# Untitled

unknown
plain_text
20 days ago
1.6 kB
0
Indexable
Never
```public class Solution {

static Scanner sc;
static Type[] runs;
static boolean[] visited;
static int minTime = 0;
static int M, D;

static public void main(String[] args) throws Exception {
sc = new Scanner(System.in);

int T = sc.nextInt();

for (int tc = 1; tc <= T; tc++) {
M = sc.nextInt();
D = sc.nextInt();

runs = new Type[5];
visited = new boolean[6];
minTime = 99999;

for (int i = 0; i < 5; i++) {
int mm = sc.nextInt();
int ss = sc.nextInt();
int mana = sc.nextInt();
runs[i] = new Type(mm * 60, ss, mana);
}

// so thu tu chay, mana, quang duong
backtrack(0, 0, M, 0);
System.out.print("Case #" + tc + "\n");
if (minTime == 99999) {
System.out.println(-1);
} else {
int mM = minTime / 60;
int sS = minTime % 60;
System.out.println(mM + " " + sS);
}
}
}

private static void backtrack(int lc, int index, int energy, int time) {
// dieu kien dung
if (minTime <= time) {
return;
}

if (energy < 0) {
return;
}

if (index == 5) {
return;
}

if (lc == D) {
minTime = Math.min(minTime, time);
return;
}

for (int i = 0; i <= 1; i++) {
if (i == 0) {
backtrack(lc, index + 1, energy, time);
} else {
int mana = runs[index].mana;
int nTime = runs[index].mm + runs[index].ss;
backtrack(lc + 1, index, energy - mana, time + nTime);
}
}
}

static class Type {
int mm, ss, mana;

public Type(int mm, int ss, int mana) {
this.mm = mm;
this.ss = ss;
this.mana = mana;
}
}
}```