Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.2 kB
14
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int energy, distance;
	static int[][] runtype = new int[5][2];
	static int minTime;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int testcase;
		testcase = sc.nextInt();
		for(int tc=1; tc<=testcase; tc++){
			energy = sc.nextInt();
			distance = sc.nextInt();
			for(int i=0; i<5; i++){
				int m,s;
				m=sc.nextInt();
				s=sc.nextInt();
				runtype[i][0] = m*60+s;
				runtype[i][1] = sc.nextInt();
			}
			minTime = Integer.MAX_VALUE;
			backtrack(0,0, 0, energy);
			System.out.println("Case #"+tc);
			if(minTime!=Integer.MAX_VALUE)
				System.out.println((minTime/60) +" "+(minTime%60));
			else
				System.out.println(-1);
		}
	}

	public static void backtrack(int ind, int count, int time, int ener){
		if(time>=minTime){
			return;
		}
		
				if(ener<0)
			return;
		
		
		if(count==distance){
			if(time<minTime)
				minTime=time;
			return;
		}
		

		for(int i=ind; i<5; i++){
//			System.out.println(count+" "+ener);
			backtrack(i, count+1, time+runtype[i][0], ener-runtype[i][1]);
		}
		
	}
}
Leave a Comment