hugo giao hang code
unknown
plain_text
5 months ago
2.5 kB
1
Indexable
Never
package practise; import java.util.Scanner; public class hugo_thi_chay { static int maxEnergy, runDist, minM, minS; static int minute = 0, second = 1, energy = 2 , typeRun = 5; static int[][] chart = new int[typeRun][3];; static int[] maxRun = new int[typeRun]; static int[] visit; // private static int calTime(int type) { // int tmp = 0 // for(int i = 0; i < visit[type]; i++) { // // } // } private static void backtrack(int type, int km, int min, int sec, int sumE) { if(km == runDist) { if(min < minM) { minS = sec; minM = min; } else if(min == minM && sec < minS) minS = sec; return; } if(type == typeRun - 1) { visit[type] = runDist - km; int tm = chart[type][minute] * visit[type]; int ts = chart[type][second] * visit[type]; int te = chart[type][energy] * visit[type]; if(sumE + te < maxEnergy) { tm = tm + min +(sec + ts)/60; ts = (sec + ts) % 60; if(tm < minM) { minS = ts; minM = tm; } else if(tm == minM && ts < minS) minS = ts; } return; } if(min > minM || (sec > minS && min == minM)) return; int tmp = maxRun[type] < runDist ? maxRun[type] : runDist; int tm = 0, ts = 0, te = 0; for(int i = 0; i <= tmp - km; i++) { visit[type] = i; tm = chart[type][minute] * i; ts = chart[type][second] * i; te = chart[type][energy] * i; if(sumE + te < maxEnergy) { tm = tm + min +(sec + ts)/60; ts = (sec + ts) % 60; backtrack(type + 1, km + i, tm, ts, sumE + te); } else return; } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int testcase = sc.nextInt(); for(int tc = 1; tc <= testcase; tc++) { maxEnergy = sc.nextInt(); runDist = sc.nextInt(); boolean flag = false; int cond = maxEnergy / runDist + 1; for(int i = 0; i < typeRun; i++) { chart[i][minute] = sc.nextInt(); chart[i][second] = sc.nextInt(); chart[i][energy] = sc.nextInt(); if(chart[i][energy] < cond) flag = true; maxRun[i] = maxEnergy / chart[i][energy]; } visit = new int[typeRun]; minM = Integer.MAX_VALUE; minS = Integer.MAX_VALUE; System.out.println("Case #" + tc); if(!flag) { System.out.println(-1); } else { backtrack(0, 0, 0, 0, 0); System.out.println(minM + " " + minS); } // return; } } }