Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
2
Indexable
Never
// hugo chay
package bla;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int nangLuong;
	static int quangDuong;
	static long ans;
	static int [][] arr;
	public static void backTrack(int k , int qd , int nl , int time){
		if(nl > nangLuong){
			return;
		}
		if(time > ans){
			return;
		}
//		if(qd > quangDuong){
//			return;
//		}
		if(k == 5){
			if(qd == quangDuong && time < ans){
				ans = time;
			}
			return;
		}
		for (int i = 0; i <= quangDuong; i++) {
			backTrack(k+1, qd + i, nl + (i*arr[k][1]), time + (i*arr[k][0]));
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			nangLuong = sc.nextInt();
			quangDuong = sc.nextInt();
			arr = new int [5][2];
			for (int i = 0; i < 5; i++) {
				int phut = sc.nextInt();
				int giay = sc.nextInt();
				int nl = sc.nextInt();
				arr[i][0] = phut*60 + giay;
				arr[i][1] = nl;
			}
			ans = Long.MAX_VALUE;
			backTrack(0, 0, 0, 0);
			if(ans == Long.MAX_VALUE){
				System.out.println("Case #"+tc);
				System.out.println("-1");
			}else{
				System.out.println("Case #"+tc);
				System.out.println(ans/60+" "+ans%60);
			}
		}
	}
}
//
4

297 10

5 38 23 5 22 12 4 16 6 5 38 20 0 20 17

192 10

2 6 12 6 5 24 2 22 22 4 13 12 4 30 16

503 10

1 42 20 1 8 14 0 33 15 2 6 6 5 3 16

122 10

2 37 21 3 59 22 6 0 22 4 56 5 0 9 10
//

Case #1
3 20
Case #2
21 0
Case #3
5 30
Case #4
1 30