# Untitled

unknown
plain_text
19 days ago
1.5 kB
0
Indexable
Never
```public class Solution {
static int T, g;
static int gate[][], min;
static int sg[], count[];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
g = sc.nextInt();
gate = new int[g][2];
for (int i = 0; i < g; i++) {
gate[i][0] = sc.nextInt();
gate[i][1] = sc.nextInt();
}

min = 123456789;
sg = new int[g];
count = new int[g];
backTrack(0, 0);
System.out.println("#" + tc + " " + min);
}
}

public static void backTrack(int k, int sum) {
if (sum >= min)
return;
if (k == g) {
if (sum < min)
min = sum;
return;
}
backTrack(k + 1, sum + gate[k][1]);
sg[k] += gate[k][0];
backTrack(k + 1, sum + 2 * gate[k][1]);
sg[k] -= gate[k][0];
int number = 0;
int tc[] = new int[21];
int ts[] = new int[21];
for (int i = 0; i < k; i++) {

tc[i] = count[i];
ts[i] = sg[i];
if (tc[i] < 3 && ts[i] > 0)
number += sg[i];
}
if (number < gate[k][0])
return;
int ss = gate[k][0];
for (int i = 0; i < k; i++) {
if (count[i] >= 3 || sg[i] <= 0)
continue;
int m = ss;
ss -= sg[i];
sg[i] -= m;

if (ss <= 0)
break;
}
for (int i = 0; i < k; i++) {
if (count[i] < 3 && sg[i] > 0)
count[i]++;
}
backTrack(k + 1, sum);
for (int i = 0; i < k; i++) {
count[i] = tc[i];
sg[i] = ts[i];
}
}
}```