Untitled
unknown
plain_text
10 months ago
49 kB
9
Indexable
Never
// Turn Over Game
As in , there is a 4×4 sized table. In a grid of the table, there are white or black stones. When you choose a position of stone randomly, the stone and four stones adjacent to the up, down, left and right sides of the stone will turn to the opposite color like turning a white stone to a black & a black stone to a white. Let’s suppose this process as a calculation.
Using such a calculation, you want to change all the stones on the table into all whites or all blacks. Find out the minimum operation count at this time.
Time limit: 1 second (java: 2 seconds)
[Input]
Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row.
Table info is given without blank over four rows per each test case. Colors are indicated like white for ‘w’ and black for ‘b’.
[Output]
Output the minimum operation count to change all colors as white or black on the first row per each test case. If not possible, output "impossible" .
** Solution **
import java.util.Scanner;
public class Solution {
static int T, count, min;
static int map[][];
static int dx[] = {0, -1, 0, 1};
static int dy[] = {-1, 0, 1, 0};
public static boolean checkFull(){
int countMap = 0;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(map[i][j] == map[0][0]) countMap++;
}
}
if(countMap == 16) return true;
return false;
}
public static void turnColor(int r, int c){
int nr, nc;
if(map[r][c] == 'b') map[r][c] = 'w';
else map[r][c] = 'b';
for(int i = 0; i < 4; i++){
nr = r + dx[i];
nc = c + dy[i];
if(0 <= nr && nr < 4 && 0 <= nc && nc < 4){
if(map[nr][nc] == 'b') map[nr][nc] = 'w';
else map[nr][nc] = 'b';
}
}
}
public static void backTrack(int k){
if(checkFull()){
if(count < min) min = count;
return;
}
if(k == 16 || count >= min) return;
int r = k/4;
int c = k%4;
count++;
turnColor(r, c);
backTrack(k+1);
count--;
turnColor(r, c);
backTrack(k+1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
map = new int[4][4];
for(int i = 0; i < 4; i++){
String S = scanner.next();
for(int j = 0; j < 4; j++){
map[i][j] = S.charAt(j);
}
}
count = 0;
min = 100;
backTrack(0);
if(min < 100){
System.out.println("Case #" + tc);
System.out.println(min);
}
else{
System.out.println("Case #" + tc);
System.out.println("impossible");
}
}
}
}
50
wbwb
wbbw
wbww
wbww
bbwb
bbbw
wbww
bwwb
bbbb
wwbw
bwbb
bbbb
bwwb
bwww
wwbb
wbbb
wbbb
bbww
bbwb
wwbw
wbwb
bwww
bwbw
wwbw
wbww
wbww
bbbw
bwwb
wbbw
wbwb
bbbb
wbww
wbww
wbwb
wwww
bwwb
bwwb
bbww
bwww
bbbw
bwbw
wwbw
wwww
wbww
bwbb
bwww
bwbb
wwww
wbbw
bbbb
bwww
bbww
wbwb
bwbw
bwbw
bwbw
bbww
bbwb
bbbw
wwwb
bwbb
wbbw
wwww
bwbb
bbww
wbbw
bbbw
wbbw
bwbb
bbww
wbww
wbbb
bwwb
bbww
wwww
wwbw
bbbb
bwbb
wwww
bwww
bwbw
wwbw
wwbb
wwww
bwww
bwbb
bbwb
wwwb
wwww
bwbw
bbbb
wbww
bwbb
wwwb
wbww
bwwb
bwww
bbwb
wwbb
bbwb
wbww
bwww
wbww
bwwb
bwbb
wbbw
bwwb
wbww
bbbw
wwww
wwbw
wbbw
wwbw
bbbw
bwwb
wbbb
bwbw
bwbb
bbwb
bwbw
bwww
wwww
bbbw
wwbw
wbww
wbww
wbbb
wbbw
bbbb
wwww
bbbb
bwwb
wwww
wbwb
wbwb
bwwb
bbwb
bbww
bbbb
bwwb
wwww
wwbb
wbbw
wbww
bbwb
wwww
wwww
wwww
wwww
wwww
bwbb
bbww
bwbb
wwww
wbbb
bwww
bwbw
wwbb
wbww
bbbb
bwww
wbwb
wwbb
wbbb
wbww
wwbb
bbbw
wbwb
wwwb
bbbw
bwww
wwwb
bwbb
bwbb
wwww
wbwb
wbbw
bwwb
bbbw
bbww
wbwb
bwbw
wwbb
wbwb
bwbb
bbbb
wbwb
bwwb
bwbw
bwwb
bwbw
bwww
bwbw
wwww
bbwb
bwwb
bbbb
bbbb
bbbb
bbbb
//Painting
The design team at SAMSUNG Electronics considers an innovative design for a new product.
The left figure is the basic diagram and the design team tries to distinguish each area marked by letter of the alphabet with four colors.
When proceeding with this, the design team pursues perfection by researching the combinations of all colors and chooses one of them.
However, they have trouble because they do not know the total number of cases of the color combinations.
Due to this difficulty, you convert the basic diagram on the left to the graph in the center and then you solve the problem by converting it to the adjacency matrix on the right.
The number of cases is 264.
What is the method used to solve this? (Time Limit : 2 seconds)
[Input]
The adjacency matrix about a basic diagram is entered.
On the first line, the number of the test cases (1<=T <= 10) is given.
On the first line of each test case, the size of the matrix n (1<=n <= 30, n is the positive number).
From the second line, the values of matrix are entered by being distinguished as one blank or other.
[Output]
For each test case, you should print "Case #T" in the first line where T means the case number.
In the second line, print out the total number of cases to paint and distinguish them with four colors for each area.
// Solution
import java.util.Scanner;
public class Solution {
static int T, N ,value, count;
static int map[][], index[], Color[];
public static boolean check(int node, int color){
for(int k = 0; k < index[node]; k++){
if(color == Color[map[node][k]]) return false;
}
return true;
}
public static void backTrack(int node){
if(node == N){
count++;
return;
}
for(int i = 1; i <= 4; i++){
if(check(node, i)){
Color[node] = i;
backTrack(node+1);
Color[node] = 0;
}
}
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
map = new int[N][N]; // Luu cac o lien ke o dang xet
index = new int[N];
Color = new int[N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
value = scanner.nextInt();
if(value == 1){
map[i][index[i]++] = j;
}
}
}
count = 0;
backTrack(0);
System.out.println("Case #" + tc);
System.out.println(count);
}
}
}
50
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 1 0 0 0 0 0 1 0
0 1 0 0 1 1 0 1 0 1 0 1 0 1 1
0 0 1 1 0 1 1 0 0 1 1 1 1 1 1
0 1 0 1 1 0 0 1 0 0 1 1 1 0 0
0 1 1 0 1 0 0 0 0 1 1 1 0 0 0
0 0 1 1 0 1 0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 1 0 1 1 0 1 1 0 0 1 0 0 1 0
0 1 0 0 1 1 1 0 1 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 0 0 1 0 0 1
0 1 1 1 1 0 0 1 0 1 0 0 0 0 1
0 1 0 1 1 0 0 1 0 0 0 0 1 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1 1 1 0 1 1 1 0
0 0 0 0 1 0 0 1 0 0 1 0 0 1 1
0 0 1 0 1 0 0 0 0 0 1 1 1 0 0
0 1 0 0 1 1 0 0 1 1 1 0 1 1 0
0 0 0 0 1 0 0 1 0 0 1 1 0 1 0
0 0 0 0 1 0 0 1 0 0 1 0 0 1 0
0 1 0 0 0 1 1 1 1 1 0 1 1 0 1
0 0 1 0 1 0 1 0 1 0 1 0 1 1 0
0 1 0 0 1 0 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 1 1 1 0 1 1 0 0
0 0 1 0 0 1 0 0 0 0 1 0 0 0 0
18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0
0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0
0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0
0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1
0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0
0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1
0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 1
0 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0
0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1
0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1
0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 1 0
0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0
0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0 0 1 1 0 1 1 1
0 1 0 1 1 0 0 0 0 1 0 1 0 0 1
0 1 1 0 0 0 1 1 0 0 1 1 1 0 1
0 0 1 0 0 1 1 1 1 0 1 0 1 0 1
0 1 0 0 1 0 0 0 0 0 0 1 1 0 1
0 1 0 1 1 0 0 1 1 0 0 0 0 0 0
0 0 0 1 1 0 1 0 1 1 1 0 1 0 1
0 0 0 0 1 0 1 1 0 1 0 0 1 1 0
0 1 1 0 0 0 0 1 1 0 0 1 0 1 1
0 1 0 1 1 0 0 1 0 0 0 1 1 1 1
0 0 1 1 0 1 0 0 0 1 1 0 1 0 0
0 1 0 1 1 1 0 1 1 0 1 1 0 0 0
0 1 0 0 0 0 0 0 1 1 1 0 0 0 0
0 1 1 1 1 1 0 1 0 1 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 1 1 0 0 1 1 1 0 1 1 0 0
0 0 1 0 0 0 1 0 1 1 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 1
0 0 0 1 1 0 0 1 0 1 0 0 0 1 1
0 1 1 0 0 0 1 0 1 1 1 0 1 0 1
0 0 1 1 0 1 0 1 0 0 1 0 1 0 1
0 0 1 1 0 1 1 1 0 0 1 1 0 1 1
0 0 0 0 1 0 0 1 1 1 0 1 1 0 0
0 0 1 0 1 0 0 0 0 1 1 0 0 0 0
0 1 1 1 1 0 0 1 1 0 1 0 0 1 0
0 0 0 0 1 0 1 0 0 1 0 0 1 0 1
0 1 0 0 0 1 1 1 1 1 0 0 0 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 0
0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1
0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0
0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1
0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0
0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1
0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1
0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1
0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0
0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0
18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0
0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0
0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 1
0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0
0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0
0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0
0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0
0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0
0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0
0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1
0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0
0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1
0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1
0 0 0 0 1 1 1 0 1 0 0 1 1 0 0 1
0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1
0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 0
0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1
0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1
0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0
0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0
0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0
0 1 0 0 1 0 0 0 0 1 0 0 1 0 1 0
0 1 1 0 0 1 1 0 0 1 0 0 0 0 0 0
0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1
0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1
0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0
0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0
0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0
0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0
0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1
0 1 0 1 1 0 1 0 0 1 1 0 0 1 1 1
0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1
0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1
0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0
0 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1
0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0
0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0
0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1
0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 1 0 0 0 1 1 0
0 0 0 0 0 0 0 1 1 0 0 0 1 1 1
0 0 0 0 0 0 1 1 1 0 1 0 1 1 0
0 1 0 0 0 0 1 1 1 0 0 1 0 1 1
0 1 0 0 0 0 0 1 1 0 1 1 0 0 0
0 0 0 1 1 0 0 1 0 1 0 0 1 0 0
0 0 1 1 1 1 1 0 1 1 0 0 0 0 0
0 1 1 1 1 1 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 1 0 1
0 0 0 1 0 1 0 0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0 1 0 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 1 1 0 1 0
0 1 1 1 1 0 0 0 0 0 0 1 1 0 0
0 0 1 0 1 0 0 0 0 1 0 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0 1 1 1 1 0
0 0 0 1 0 0 0 0 0 1 1 0 0 1 0
0 0 1 0 1 0 1 0 0 0 0 1 0 1 1
0 0 0 1 0 0 1 0 1 1 1 1 1 1 1
0 1 0 0 0 0 0 1 1 1 1 0 1 0 0
0 1 0 1 1 0 0 0 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0 1 1 0 0 0 0 0
0 1 0 0 1 1 0 1 0 0 0 1 0 1 1
0 0 1 0 1 1 0 1 0 0 0 0 0 1 1
0 1 1 0 1 1 0 0 0 0 0 1 0 1 0
0 1 0 1 1 0 1 0 1 0 1 0 1 1 1
0 1 0 0 1 1 0 0 0 0 0 1 0 0 1
0 1 1 1 1 0 0 0 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 1 1 0 1 1 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 1 0 0 0 0 1 0
0 1 0 1 0 1 0 0 0 0 1 1 1 0 1
0 0 1 0 0 1 0 0 1 1 1 0 0 0 0
0 0 0 0 0 1 1 1 0 0 1 1 1 0 1
0 0 1 1 1 0 1 0 1 1 1 0 0 0 1
0 1 0 0 1 1 0 0 0 0 0 0 1 0 1
0 0 0 0 1 0 0 0 1 0 0 0 0 1 1
0 1 0 1 0 1 0 1 0 0 0 0 0 1 0
0 0 0 1 0 1 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 0 0 0 0 1 1 1 0
0 0 1 0 1 0 0 0 0 0 1 0 0 0 1
0 0 1 0 1 0 1 0 0 1 1 0 0 1 1
0 1 0 0 0 0 0 1 1 1 1 0 1 0 1
0 0 1 0 1 1 1 1 0 0 0 1 1 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 1 1 1 0 0 1 0 0 0 1
0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0
0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0
0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0
0 1 1 1 0 1 0 1 0 0 1 1 0 0 1 1
0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0
0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0
0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0
0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1
0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1
0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0
0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1
0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 0 1 0 1 1 1 1
0 0 0 1 1 1 1 0 1 1 1 0 0 1 0
0 1 1 0 0 0 0 0 1 0 1 0 0 0 1
0 1 1 0 0 0 0 0 1 1 1 0 0 0 0
0 0 1 0 0 0 0 0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 1 1 1
0 1 0 0 0 0 1 0 0 1 1 0 1 0 0
0 0 1 1 1 1 0 0 0 1 0 1 1 0 0
0 1 1 0 1 0 0 1 1 0 1 0 1 0 0
0 0 1 1 1 1 0 1 0 1 0 0 1 1 0
0 1 0 0 0 0 0 0 1 0 0 0 0 1 0
0 1 0 0 0 0 1 1 1 1 1 0 0 1 0
0 1 1 0 0 0 1 0 0 0 1 1 1 0 0
0 1 0 1 0 0 1 0 0 0 0 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 1 0 1 1 1 0 0 0
0 1 0 1 0 0 0 1 0 1 1 0 0 1 0
0 0 1 0 1 0 0 0 1 1 0 0 0 0 0
0 1 0 1 0 0 1 0 0 1 0 0 1 1 1
0 1 0 0 0 0 1 0 1 1 0 0 1 1 0
0 0 0 0 1 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 1 0 1 0 0 0 1 0 0 0 0 1
0 1 1 1 1 1 1 0 1 0 0 1 1 1 1
0 1 1 0 0 0 0 0 0 0 0 0 0 1 1
0 1 0 0 0 0 0 1 0 1 0 0 1 0 1
0 0 0 0 1 1 0 0 0 1 0 1 0 1 0
0 0 1 0 1 1 0 0 0 1 1 0 1 0 0
0 0 0 0 1 0 0 1 1 1 1 1 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 1 1 0 1 0 1 1
0 0 0 0 1 1 1 1 0 0 1 0 0 1 0
0 0 0 0 1 1 1 1 1 0 0 0 1 1 1
0 0 1 1 0 0 0 0 1 0 1 0 0 1 0
0 1 1 1 0 0 1 0 0 0 0 1 0 1 1
0 0 1 1 0 1 0 0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0 0 0 1 0 1 0 0
0 1 0 1 1 0 1 0 0 0 0 1 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 1 0 1 0 1 1 0 0 0 0 1 0 1
0 1 0 0 0 1 0 0 1 1 0 0 1 0 1
0 0 0 1 0 0 0 1 0 0 1 1 0 0 1
0 1 1 1 1 1 0 0 1 1 0 0 0 0 0
0 1 0 1 0 1 0 0 0 1 1 1 1 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 1 0 0
0 0 0 0 1 1 0 0 1 0 0 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 1 0 0 1 0 0 1 0
0 0 1 0 0 0 0 1 0 0 0 0 1 0 1
0 1 0 0 1 0 0 0 1 0 1 1 0 0 1
0 1 0 0 1 1 0 0 1 1 0 0 1 0 0
0 0 1 1 0 0 1 1 0 0 1 1 0 1 0
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1
0 0 0 0 1 0 1 0 1 1 0 1 1 1 1
0 0 1 0 0 0 1 0 1 0 1 0 0 1 1
0 1 0 0 0 1 0 1 0 0 1 0 0 1 0
0 0 0 0 1 0 0 0 1 0 1 1 1 0 0
0 0 1 1 0 1 1 0 0 1 1 1 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 1 0 1 1 0 1 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0 1 0 0
0 1 0 0 1 0 1 0 1 1 1 0 0 0 0
0 1 0 1 0 0 0 1 1 0 1 1 0 0 1
0 0 1 0 0 0 0 1 1 0 1 0 0 0 1
0 1 0 1 0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 0 0 0 0 0 1 1 0
0 1 1 1 1 1 0 0 0 1 0 1 0 1 1
0 1 0 1 0 0 1 0 1 0 1 1 1 1 1
0 0 0 1 1 1 0 0 0 1 0 1 1 0 0
0 1 0 0 1 0 0 0 1 1 1 0 0 0 0
0 0 1 0 0 0 0 1 0 1 1 0 0 0 1
0 0 0 0 0 0 1 1 1 1 0 0 0 0 1
0 0 0 0 1 1 0 0 1 1 0 0 1 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0
0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0
0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
0 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1
0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1
0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0
0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0
0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1
0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0
0 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1
0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1
0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 1
0 0 0 1 1 1 1 0 1 1 0 0 0 1 0 0
0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0
0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1
0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0
0 0 1 0 0 0 0 0 1 1 0 1 1 1 1 1
0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1
0 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0
0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0
0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1
0 1 0 0 1 0 1 1 0 0 1 0 1 1 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 1 1 0 0 1 1 0 1 1 0 1 0
0 0 1 0 0 1 0 1 1 1 0 1 1 0 1
0 0 1 0 0 1 1 0 1 1 0 1 1 1 1
0 0 0 1 1 0 0 0 0 1 1 1 1 1 0
0 0 0 0 1 0 0 0 0 0 1 1 1 0 0
0 0 1 1 0 0 0 0 0 0 1 1 0 1 0
0 0 1 1 1 0 0 0 0 0 1 0 1 0 1
0 0 0 1 1 1 0 0 0 0 0 0 1 1 0
0 1 1 0 0 1 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 0 0 0 0 0 0 1
0 0 0 1 1 1 1 0 1 1 0 0 0 0 1
0 0 1 0 1 1 0 1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0 1 0 0 1 1 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 0 0 0 0 0 1 0 1
0 1 0 0 1 1 0 0 0 0 0 0 1 1 0
0 1 0 0 0 0 1 1 0 1 0 0 0 1 0
0 0 1 0 0 0 0 0 0 1 1 0 1 0 1
0 0 1 0 0 0 0 1 0 0 0 1 1 0 1
0 1 0 1 0 0 0 1 0 1 1 1 1 1 1
0 0 0 1 0 1 1 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 1 1 0
0 0 0 1 1 0 1 0 1 0 0 1 1 1 1
0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 1 0 0 1 1 0
0 1 1 0 1 1 1 1 1 1 0 1 0 0 0
0 0 1 1 0 0 1 1 1 1 0 1 0 0 1
0 1 0 0 1 1 1 1 0 1 0 0 0 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0
0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0
0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0
0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0
0 1 0 0 0 1 0 1 1 0 0 1 1 1 0 1
0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1
0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0
0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0
0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0
0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1
0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0
18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 1 1
0 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1
0 1 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 0
0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 1
0 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1
0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 0 1 0
0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1
0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0
0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1
0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0
0 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0
0 1 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0
0 1 1 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0
19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1
0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0
0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1
0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1
0 0 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0
0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 1 0
0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0
0 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0
0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0
0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 1 0 0 0 0 1
0 1 0 0 0 1 0 1 1 0 1 1 0 1 1
0 1 0 0 0 0 0 0 1 0 1 1 1 0 1
0 1 1 1 0 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 1 0 1 1 0 0 1
0 1 0 1 0 0 0 0 0 1 0 0 1 1 0
0 0 1 1 1 0 1 0 0 1 1 1 0 0 0
0 0 1 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 1 1 1 1 0 1 1 0 1 0 0 1
0 0 0 1 1 0 1 0 1 0 1 0 0 0 1
0 0 0 0 1 0 0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 0 1 0 1
0 1 1 1 1 0 1 0 0 0 1 1 0 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 1 0 0 1 0 1
0 1 0 0 0 0 1 1 0 1 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0 1 0 0 1 0
0 0 0 1 0 1 1 1 1 1 1 1 0 1 0
0 1 0 1 1 0 0 1 0 0 0 1 1 0 1
0 0 1 1 1 0 0 1 1 0 0 0 1 0 1
0 0 1 1 1 1 1 0 0 0 1 0 1 0 1
0 0 0 0 1 0 1 0 0 0 1 1 1 0 0
0 1 1 0 1 0 0 0 0 0 1 0 1 1 0
0 0 0 1 1 0 0 1 1 1 0 0 1 1 1
0 0 0 0 1 1 0 0 1 0 0 0 1 1 0
0 1 0 0 0 1 1 1 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 1 1 1 0 0 1
0 1 0 0 0 1 1 1 0 0 1 0 0 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1
0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0
0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0
0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1
0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 1
0 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1
0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1
0 0 0 1 0 1 0 1 1 0 0 1 0 0 0 0
0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1
0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0
0 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0
0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 0
0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 1 1 1 1 0 1 0
0 0 0 0 0 1 0 1 0 0 0 1 0 1 1
0 1 0 0 0 1 1 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 1 1 0 0 1 0 1 1 1 1 1 0 1
0 1 0 1 0 1 0 0 0 0 1 1 0 0 1
0 0 1 0 1 0 0 0 0 1 0 1 1 1 1
0 1 0 1 0 1 0 0 0 0 0 0 1 1 1
0 1 0 0 0 1 0 1 0 0 1 1 0 0 0
0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
0 1 1 0 0 1 1 1 0 1 1 0 0 0 0
0 0 0 0 1 1 0 1 1 0 0 0 0 0 1
0 1 1 1 0 0 0 1 1 0 0 0 0 0 1
0 0 1 0 1 1 1 1 1 0 1 0 1 1 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1
0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
0 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1
0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0
0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0
0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1
0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 1
0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0
0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1
0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0
0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0
19
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0
0 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 1 0 0
0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0
0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0
0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0
0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 1
0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0
0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 0
0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1
0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1
0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1
0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0
0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 0
17
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0
0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1
0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0
0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1
0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1
0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0
0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1
0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0
0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1
0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0
0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1
0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0
0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1
0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 1 0 1 1 0 0 1
0 0 0 1 1 0 0 1 1 0 0 0 0 0 0
0 1 1 0 0 1 0 1 0 0 1 1 1 0 1
0 1 1 0 0 1 0 0 1 1 1 0 0 0 1
0 0 0 1 1 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 0 0 0 1 0
0 1 1 1 0 0 0 0 0 0 0 1 0 1 1
0 1 1 0 1 0 1 0 0 1 0 1 0 1 0
0 0 0 0 1 1 1 0 1 0 1 1 0 1 0
0 1 0 1 1 0 0 0 0 1 0 0 1 0 1
0 1 0 1 0 0 0 1 1 1 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 1
0 1 0 1 1 0 0 1 0 0 1 0 0 1 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 1 0 0 1 0 0 0 0
0 1 0 0 1 1 1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 1 0 0 1 1 0 0 0 0
0 0 1 1 0 0 1 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 1 0 0 0 0 0
0 1 1 1 1 0 0 1 1 1 0 1 1 1 1
0 1 0 0 0 0 1 0 0 0 1 1 0 1 0
0 0 1 0 0 1 1 0 0 0 0 1 1 0 1
0 0 0 1 0 1 1 0 0 0 1 1 1 0 0
0 1 1 1 0 0 0 1 0 1 0 1 1 0 0
0 0 0 0 0 0 1 1 1 1 1 0 0 0 0
0 0 1 0 1 0 1 0 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1
0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1
0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0
0 0 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0
0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 0
0 0 0 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0
0 0 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0
0 0 1 1 1 0 1 0 0 0 0 1 1 1 0 0 0 1
0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0
0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0
0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0
0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1
0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1
0 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1
0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
17
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0
0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1
0 1 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1
0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0
0 0 1 0 0 0 0 0 1 1 1 0 1 1 1 1 1
0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0
0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1
0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1
0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0
0 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0
0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0
0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1
0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1
0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1
0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0
0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0
0 0 0 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1
0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0
0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 1
0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0
0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0
0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0
0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1
0 1 0 0 0 1 0 1 1 1 1 1 0 0 0 1
0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1
0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 1 1 1 0 0 0 0 1 1
0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0
0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1
0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1
0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 1
0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1
0 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1
0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1
0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1
0 0 1 0 1 1 0 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1
0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0
0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0
17
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0
0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1
0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1
0 1 1 0 0 0 0 0 0 1 0 1 0 0 1 0 1
0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1
0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1
0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1
0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0
0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1
0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0
0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1
0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0
0 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 0
0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1
0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0
0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0
0 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1
0 1 1 0 0 1 0 0 0 0 0 0 0 1 0 1
0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0
0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0
0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0
0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0
0 0 1 0 0 0 0 1 1 1 0 0 1 0 1 1
0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1
0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0
0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
0 1 0 1 0 1 1 1 0 0 0 0 0 0 0
0 1 1 0 1 0 1 1 0 0 0 0 1 1 1
0 0 0 1 0 0 1 0 1 0 1 1 0 0 1
0 1 1 0 0 0 0 1 0 0 1 0 1 1 0
0 0 1 1 1 0 0 0 1 0 1 0 0 0 0
0 1 1 1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 1 0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0
0 0 0 0 1 1 1 0 1 1 0 1 0 0 1
0 1 0 0 1 0 0 0 1 0 1 0 1 0 0
0 1 0 1 0 1 0 0 1 0 0 1 0 0 1
0 1 0 1 0 1 0 0 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 1 0 1 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1
0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1
0 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0
0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0
0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0
0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1
0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0
0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0
0 0 0 1 0 0 1 1 0 1 1 0 1 0 0 0
0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1
0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0
0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0
0 0 0 1 0 1 0 1 1 0 1 0 1 0 1 0
0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0
0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0
0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1
0 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0
0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1
0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0
0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1
0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0
0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0
0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 1 1 0 0
0 1 0 1 0 1 1 0 0 0 1 0 1 0 1
0 0 1 0 1 1 1 0 0 1 0 0 1 0 1
0 0 0 1 0 0 0 1 0 1 0 1 1 0 0
0 0 1 1 0 0 0 1 0 0 0 1 1 0 1
0 0 1 1 0 0 0 1 1 0 1 1 1 0 0
0 1 0 0 1 1 1 0 1 0 0 1 1 0 0
0 0 0 0 0 0 1 1 0 0 0 1 0 1 1
0 0 0 1 1 0 0 0 0 0 0 1 0 1 0
0 0 1 0 0 0 1 0 0 0 0 0 1 1 0
0 1 0 0 1 1 1 1 1 1 0 0 0 1 0
0 1 1 1 1 1 1 1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0
0 0 1 1 0 1 0 0 1 0 0 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 1 1 0 0 1 1 1 1 0
0 1 0 0 0 0 0 1 1 0 0 0 1 1 0
0 0 0 0 0 1 0 0 0 0 0 1 0 1 1
0 1 0 0 0 1 0 0 1 0 1 0 1 1 0
0 1 0 1 1 0 0 1 1 1 0 0 0 1 1
0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
0 1 1 0 0 1 1 0 0 0 0 1 0 1 0
0 0 1 0 1 1 1 0 0 1 0 1 1 1 1
0 0 0 0 0 1 0 0 1 0 1 0 0 0 1
0 1 0 0 1 0 1 0 0 1 0 0 0 0 1
0 1 0 1 0 0 0 1 1 0 0 0 1 0 1
0 1 1 0 1 0 0 0 1 0 0 1 0 0 1
0 1 1 1 1 1 0 1 1 0 0 0 0 0 0
0 0 0 1 0 1 1 0 1 1 1 1 1 0 0
18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 0
0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 1 1
0 1 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0
0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0
0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 0 1
0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0
0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0
0 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0
0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 1
0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0
0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0
0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 1 0 0 1 0 0 1
0 0 0 0 1 1 0 0 0 1 0 1 1 1 0
0 1 0 0 0 0 1 0 0 1 1 0 0 1 0
0 0 1 0 0 0 1 0 0 1 0 0 1 0 1
0 0 1 0 0 0 1 0 1 1 1 0 1 1 0
0 1 0 1 1 1 0 1 0 1 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1 0 0 1 1
0 1 0 0 0 1 0 0 0 1 0 1 0 1 1
0 0 1 1 1 1 1 0 1 0 1 0 0 1 0
0 0 0 1 0 1 1 1 0 1 0 1 1 1 1
0 1 1 0 0 0 1 0 1 0 1 0 0 0 0
0 0 1 0 1 1 0 0 0 0 1 0 0 1 0
0 0 1 1 0 1 0 1 1 1 1 0 1 0 0
0 1 0 0 1 0 0 1 1 0 1 0 0 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1
0 0 0 1 1 0 1 0 1 1 1 0 1 1 1 0
0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0
0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0
0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1
0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0
0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0
0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0
0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1
0 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0
0 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1
0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0
0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1
0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0
18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1
0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0
0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1
0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1
0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 0 1 1
0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0
0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0
0 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0
0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0
0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1
0 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0
0 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 0
16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 1
0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1
0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0
0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0
0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0
0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1
0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0
0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0
0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1
0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0
0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1
0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1
0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0
Nâng cấp máy tính
Time limit: 1 giây với C/C++, 2 giây với Java.
Submission limit: 5 lần.
Memory limit: 256MB cho tổng cộng các vùng nhớ heap, global và static (chỉ 1MB cho vùng nhớ stack).
Anh Kim có 1 máy tính đã mua từ thời sinh viên nên hiện giờ cần phải nâng cấp và thay thế L linh kiện để đảm bảo máy tính hoạt động tốt.
Để tìm mua được các thiết bị đó với giá tốt nhất anh Kim đã qua chợ Trời và tham khảo được giá của tất cả N thiết bị của máy tính.
Không chỉ thế, anh đã tìm kiếm thêm trên mạng, và anh rất vui khi có M gói ưu đãi giá rẻ được rao bán trên mạng, mỗi gói có giá bán là P bao gồm K thiết bị của máy tính.
Anh Kim có thể mua một hoặc nhiều gói ưu đãi và có thể mua thừa linh kiện chưa cần thay thế.
Hãy giúp anh Kim mua được đủ L thiết bị cần thiết với tổng giá thành là nhỏ nhất.
Input
Dòng đầu tiên là số lượng test case T (T <= 50).
Mỗi test case gồm các thông tin sau:
- Dòng đầu tiên là số nguyên dương N (1 <= N <= 20) là số lượng thiết bị chính của máy tính.
- Dòng thứ 2 bao gồm N số, số thứ i tương ứng là giá của thiết bị thứ i được bán ở chợ Trời.
- Dòng thứ 3 là số nguyên dương M ( 0 <= M <= 30) là số lượng gói ưu đãi có trên mạng.
- M dòng tiếp theo, mỗi dòng thứ i là thông tin về gói ưu đãi thứ i. Số đầu tiên là giá của gói ưu đãi P ( 1 <= P <= 1000), số tiếp theo là số lượng thiết bị K ( 1 <= K< = N) trong gói ưu đãi đó,
K số tiếp theo là các thiết bị có trong gói ưu đãi đó.
- Dòng cuối cùng của mỗi test case là thông tin về các thiết bị mà anh Kim cần mua. Số đầu tiên là số lượng thiết bị L, L số tiếp theo là các thiết bị anh Kim cần mua
- Các thiết bị được đánh số trong đoạn từ 1 đến N và không có số nào trùng nhau
Output
Bắt đầu mỗi test case là "#x" với x là số thứ tự của test case (bắt đầu từ 1), tiếp theo là một dấu cách và giá thành nhỏ nhất mà anh Kim cần bỏ ra để mua đủ những thiết bị anh cần.
Sample
Input
1 <-- T = 1,
5 <-- Số linh kiện chính của máy tính
20 15 17 18 25 <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng
4 <-- 4 gói ưu đãi trên mạng
30 3 1 2 5 <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5
25 2 2 3 <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3
35 3 1 3 5 <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5
20 2 3 4 <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4
3 2 4 5 <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5
Output
#1 48
Giải thích: Để mua được 3 thiết bị 2, 4, 5 với giá rẻ nhất, ta sẽ mua gói giá rẻ 1 gồm 1, 2, 5 với giá 30 và mua thiết bị 4 ở chợ Trời với giá 18, tổng là 30 + 18 = 48.
// Solution
import java.util.Scanner;
public class Solution{
static int T, numer_Device, skyMarket[];
static int M, K, pack_Discount[][], value_Pack[], number_Pack[];
static int L, device_Need[];
static int sum, min;
static boolean visitPackage[];
public static void backTrack(int k){
if(k == L){
if(sum < min) min = sum;
return;
}
if(sum > min) return;
//Mua thiet bi cho troi
sum += skyMarket[device_Need[k]-1];
backTrack(k+1);
sum -= skyMarket[device_Need[k]-1];
for(int i = 0; i < M; i++){
for(int j = 0; j < number_Pack[i]; j++){
if(pack_Discount[i][j] == device_Need[k]){
if(!visitPackage[i]){
sum += value_Pack[i];
visitPackage[i] = true;
backTrack(k+1);
sum -= value_Pack[i];
visitPackage[i] = false;
}
else{
backTrack(k+1);
}
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
numer_Device = scanner.nextInt();
skyMarket = new int[numer_Device];
for(int i = 0; i < numer_Device; i++){
skyMarket[i] = scanner.nextInt();
}
M = scanner.nextInt(); // So goi uu dai
visitPackage = new boolean[M];
pack_Discount = new int[M][numer_Device]; // Luu co thiet bi nao trong goi
value_Pack = new int[M];
number_Pack = new int[M];
for(int i = 0; i < M; i++){
value_Pack[i] = scanner.nextInt(); // Gia cua goi
K = scanner.nextInt(); // So luong thiet bi trong goi
number_Pack[i] = K;
for(int j = 0; j < K; j++){
pack_Discount[i][j] = scanner.nextInt();
}
}
L = scanner.nextInt(); // So luong thiet bi Kim can mua
device_Need = new int[L];
for(int i = 0; i < L; i++){
device_Need[i] = scanner.nextInt();
}
min = 1000000;
backTrack(0);
System.out.println("#" + tc + " " + min);
}
}
}
50
10
68 63 83 94 55 35 12 63 30 17
4
104 3 2 6 3
31 3 2 5 3
81 4 3 2 7 9
42 1 7
6 9 10 3 8 6 5
4
40 52 12 94
2
58 2 1 4
15 1 2
3 4 2 3
8
61 91 11 32 33 59 77 24
5
81 2 2 3
13 3 6 2 5
78 2 5 3
9 1 7
9 1 5
4 8 3 4 2
11
61 9 82 30 86 58 34 31 19 30 93
12
24 2 3 8
151 3 11 4 9
142 3 7 3 10
18 2 7 6
207 5 8 5 7 2 11
65 2 11 8
16 3 3 1 11
36 1 2
150 4 10 7 2 8
3 1 8
20 1 2
138 5 11 5 8 6 7
6 3 10 9 1 5 8
3
11 72 66
8
8 1 2
3 1 1
18 1 2
32 1 3
19 1 3
28 1 2
34 1 2
15 1 2
1 1
6
32 4 11 99 24 55
3
40 1 1
111 3 6 3 2
73 2 1 5
4 3 6 5 4
9
66 61 18 58 34 75 29 36 66
6
62 2 1 4
32 1 4
22 3 5 3 1
10 1 9
25 1 9
6 4 6 1 7 8
6 2 9 8 7 5 3
4
78 46 92 82
14
68 2 3 2
129 2 2 1
28 1 4
134 2 1 4
56 2 2 3
56 2 4 2
66 1 2
68 1 4
37 1 2
41 1 3
36 2 4 2
85 2 1 2
19 2 2 3
38 1 2
2 1 3
4
57 86 72 66
0
3 1 4 2
7
93 58 20 97 20 6 90
5
122 3 1 4 7
107 3 4 5 2
18 1 6
53 3 1 5 4
18 1 1
5 7 2 1 4 3
5
36 52 59 44 35
4
43 1 2
79 2 1 4
60 2 3 2
5 1 3
2 4 5
3
45 11 21
10
20 1 2
1 1 3
9 1 3
5 1 2
11 1 2
3 1 1
5 1 2
8 1 2
28 1 2
23 1 3
1 3
10
88 37 61 62 59 64 23 76 21 52
13
122 3 9 4 1
59 3 4 7 8
44 2 6 5
47 1 7
23 1 2
40 2 8 4
37 1 5
164 4 1 2 3 10
2 1 9
158 4 8 1 9 10
17 4 8 5 9 4
38 3 1 9 4
236 5 1 2 5 6 7
7 1 4 6 7 8 2 10
9
17 15 46 85 3 84 70 73 74
2
48 2 5 4
86 4 7 3 8 4
4 2 6 3 7
4
69 79 23 69
10
9 2 3 4
82 2 4 2
21 2 3 2
85 2 3 4
56 2 3 2
49 1 2
2 1 3
21 1 1
16 2 4 3
21 1 2
2 3 1
9
42 8 84 75 48 17 28 83 96
13
66 4 9 7 2 3
154 3 7 8 4
88 3 2 4 9
24 4 6 1 2 5
86 4 7 8 4 9
30 1 2
6 4 3 2 4 6
46 2 2 8
73 2 4 2
175 4 5 2 8 4
11 3 6 7 9
96 2 1 6
20 3 4 7 6
6 6 7 5 9 4 8
8
55 7 38 12 61 22 86 2
10
34 1 4
25 2 3 7
39 2 8 2
17 2 2 5
77 2 7 2
13 4 1 8 3 4
32 2 8 1
24 2 6 5
4 4 1 8 6 2
122 4 2 5 7 1
4 6 7 3 1
3
73 47 79
14
41 1 1
18 1 1
46 1 2
11 1 2
21 1 2
31 1 1
30 1 2
7 1 3
47 1 3
10 1 3
22 1 3
25 1 2
54 1 2
23 1 1
1 2
6
98 85 36 26 55 40
5
5 2 5 6
16 1 3
56 1 2
33 1 5
21 1 5
3 4 3 1
5
10 68 3 69 1
3
30 1 3
20 2 4 1
4 1 4
2 1 2
14
43 81 53 97 77 1 95 91 84 43 57 93 70 65
16
23 1 11
11 3 2 8 10
45 3 10 2 7
179 4 3 12 13 4
14 5 8 12 4 14 2
1 3 14 1 12
56 4 4 5 2 1
6 1 9
131 7 13 9 10 4 14 3 2
213 5 3 11 4 13 6
254 6 14 1 13 5 4 10
92 2 8 6
86 2 11 8
48 3 7 9 6
179 4 9 14 12 3
74 3 8 6 7
12 13 7 9 10 4 1 11 3 2 8 12 14
14
55 92 13 59 30 53 19 23 50 99 58 80 26 94
21
126 6 9 5 6 11 2 7
43 1 4
27 7 11 10 3 14 4 6 5
141 4 1 6 7 11
249 6 4 6 8 3 9 11
61 6 13 10 9 8 12 6
366 7 3 4 13 6 7 11 12
267 7 6 7 14 5 4 12 9
171 4 5 7 11 12
56 1 12
98 2 14 6
75 5 13 10 1 14 11
5 1 6
51 5 4 1 12 8 5
97 5 12 5 4 7 13
8 4 14 12 10 9
272 7 7 3 4 2 11 6 9
77 5 13 5 6 11 4
20 6 10 4 6 8 12 5
48 7 6 5 11 10 3 14 12
190 5 2 9 7 3 6
11 9 7 3 2 13 5 11 10 12 4 1
13
95 88 64 1 73 31 9 62 7 23 90 76 64
17
115 3 1 8 9
40 1 8
165 5 3 4 10 5 1
29 1 6
188 5 11 7 9 3 4
15 2 4 11
165 6 10 4 9 3 8 2
142 3 9 13 6
47 4 13 10 12 9
8 1 7
51 6 12 11 10 4 8 6
95 4 6 2 7 12
25 1 6
70 5 13 12 10 6 1
18 2 6 4
38 1 12
54 6 5 1 13 4 3 10
11 3 5 8 7 1 12 9 10 11 6 13
13
21 1 28 39 18 17 49 1 51 80 4 86 46
18
92 4 10 8 12 3
2 2 5 8
8 1 2
34 5 11 9 6 12 7
31 2 4 8
163 5 10 12 8 6 7
94 3 13 7 2
24 6 12 7 10 8 1 9
50 2 5 4
27 1 6
4 3 10 6 13
126 6 10 8 1 5 6 4
13 4 1 8 12 4
65 2 8 10
10 1 4
19 3 6 9 5
41 1 8
11 5 5 7 6 9 4
11 3 12 7 8 5 4 1 11 2 6 10
16
26 40 28 91 6 33 14 14 53 78 58 44 73 5 59 79
14
54 2 8 1
79 5 3 12 10 15 8
82 2 4 7
154 5 4 9 14 6 13
170 4 11 9 16 8
283 6 13 4 11 1 15 10
230 6 13 3 16 14 1 6
24 4 6 10 1 5
152 5 16 11 3 12 5
90 2 10 2
195 6 7 15 13 4 12 14
24 3 2 15 6
42 6 7 3 16 9 1 11
131 3 10 16 12
9 16 2 11 8 1 15 5 14 7
17
49 14 10 49 96 65 30 71 58 76 81 41 30 41 81 71 47
5
288 6 2 10 7 4 8 9
32 3 4 11 12
45 1 7
61 4 3 9 8 12
102 2 14 5
13 10 7 14 4 9 6 12 16 3 5 13 17 11
11
87 56 8 80 47 20 29 46 50 31 66
5
7 1 9
30 4 11 2 5 3
36 1 11
47 4 2 9 3 4
36 5 11 5 2 9 1
8 4 3 11 6 1 8 10 5
15
25 77 72 41 86 41 28 82 6 11 47 16 10 51 48
1
93 3 14 6 15
7 2 14 10 8 7 4 13
13
24 62 28 37 88 62 27 5 2 22 88 93 77
17
9 4 13 10 1 12
197 5 8 3 13 11 7
92 4 7 1 4 13
20 2 6 12
113 4 7 9 6 3
165 5 5 13 10 2 9
61 2 8 4
183 4 5 6 11 13
4 5 6 13 9 1 2
75 2 1 6
81 6 8 7 2 9 1 4
176 5 4 6 2 9 8
75 3 4 6 10
46 1 7
88 2 13 8
42 2 12 1
34 2 13 5
9 11 10 7 12 2 9 4 1 6
11
27 17 58 87 28 97 29 30 57 96 39
21
8 3 5 10 11
34 5 7 4 2 10 5
105 3 11 2 6
126 4 2 7 6 3
53 4 5 4 6 10
83 3 10 5 3
20 2 11 2
76 2 10 1
89 2 1 2
19 1 6
4 4 6 3 5 2
145 4 5 1 11 9
110 4 4 11 5 10
180 4 3 4 5 10
10 1 9
264 5 8 9 2 5 4
62 4 11 10 5 9
9 1 3
19 2 1 3
98 3 10 7 1
25 5 2 10 4 3 7
7 11 8 2 1 9 4 5
17
26 67 98 58 8 61 83 45 85 14 55 7 6 28 13 47 9
20
334 8 11 13 6 10 3 1 16 8
136 4 4 14 6 17
127 3 9 2 5
36 3 4 16 15
70 4 17 4 1 16
27 8 14 5 3 11 6 10 13 7
43 2 12 17
103 4 7 4 8 9
108 6 7 8 15 3 9 5
52 2 17 6
97 4 6 7 1 9
46 1 6
144 3 3 17 1
141 8 9 12 6 5 17 3 8 2
99 8 8 9 3 16 14 4 10 2
175 8 13 11 2 1 3 8 7 4
288 7 2 7 14 3 15 16 6
103 2 10 2
159 5 14 10 6 12 7
13 2 5 7
13 5 14 16 11 13 2 3 4 1 8 9 10 15
19
75 29 39 37 75 69 3 79 95 50 94 14 33 88 9 69 34 95 78
28
370 9 5 9 13 1 15 10 17 3 11
160 6 2 14 9 4 7 12
47 1 8
100 3 17 8 9
338 7 12 17 11 2 10 5 3
86 4 4 11 15 7
41 1 10
96 2 1 11
185 5 17 18 1 7 2
37 1 13
254 8 10 14 19 1 7 12 6 13
60 2 16 19
27 1 5
202 5 17 4 13 3 14
117 6 18 11 16 17 19 7
91 4 18 5 16 13
164 6 7 2 10 14 13 19
94 3 9 13 3
39 2 6 13
237 5 8 14 11 1 16
173 4 6 14 4 5
171 6 7 5 13 2 11 4
76 2 19 5
21 6 9 15 14 3 19 10
25 2 19 9
26 8 4 18 3 9 8 13 1 17
211 7 13 17 9 2 14 10 15
174 4 11 10 3 19
13 2 8 10 15 9 3 1 12 5 18 6 7 13
13
74 14 1 44 93 77 80 76 96 88 80 95 46
15
6 4 6 4 12 7
50 2 3 8
5 1 6
136 5 10 6 12 2 7
103 6 13 2 9 1 7 8
190 5 7 2 1 3 12
167 4 2 7 11 1
89 3 3 8 11
55 4 1 7 2 10
115 6 2 6 4 1 9 8
42 5 3 13 2 6 9
18 5 5 6 4 7 9
147 6 9 2 5 3 10 6
209 6 12 13 3 10 1 5
112 6 12 11 10 13 8 2
8 1 3 12 6 11 13 2 7
16
57 37 39 8 25 26 63 85 24 12 40 34 2 28 68 15
0
14 15 7 3 6 9 1 13 16 14 5 4 12 8 11
18
9 17 68 80 94 86 9 87 28 96 35 87 61 99 95 54 52 45
4
89 6 4 13 6 3 18 14
103 2 4 9
389 8 8 16 1 15 7 18 17 11
279 7 4 11 6 1 2 13 5
15 8 12 3 4 1 11 16 14 6 7 17 2 15 13 5
12
50 31 70 44 94 35 68 57 2 46 99 75
14
84 3 1 10 8
187 6 8 10 7 2 9 1
217 5 2 5 4 12 7
177 4 3 1 10 8
217 6 3 7 4 8 5 12
131 6 10 4 9 7 6 3
172 5 9 1 3 6 5
1 4 9 5 4 1
44 2 10 2
73 4 11 1 6 4
47 3 9 5 2
24 3 9 7 3
82 2 11 8
42 3 5 4 6
11 10 7 11 6 12 1 8 2 9 4 5
12
79 39 87 87 20 54 44 88 70 58 14 66
7
67 3 7 3 5
48 2 9 1
2 1 4
12 2 6 4
73 6 1 6 11 3 9 7
18 1 3
68 6 1 12 6 10 9 11
9 10 3 6 1 7 11 4 2 9
17
46 6 41 98 77 19 82 20 24 13 33 83 24 7 68 27 38
3
88 2 10 7
233 5 8 2 1 5 13
77 3 5 6 10
8 7 3 16 2 9 8 10 13
14
42 27 19 12 59 88 93 39 35 78 39 81 26 81
15
18 1 4
3 3 9 7 1
16 5 9 8 2 10 14
120 3 2 14 9
34 1 4
38 7 13 14 5 4 3 10 2
95 5 9 7 11 14 10
17 1 11
156 7 6 7 8 11 3 5 9
34 1 6
13 2 6 9
51 4 11 7 6 10
182 5 7 12 9 6 1
49 2 1 4
58 4 9 8 12 6
7 2 11 3 7 14 10 8
19
87 35 43 52 35 88 79 32 85 56 6 79 34 58 27 24 76 70 61
18
110 6 16 6 17 9 7 4
183 6 5 15 19 14 1 2
25 1 3
1 1 7
367 8 19 14 8 16 18 7 17 1
116 3 4 14 18
165 5 19 18 17 1 13
32 1 2
8 1 7
96 3 17 13 7
52 3 17 10 18
20 1 1
23 3 3 16 1
28 1 7
135 6 15 4 18 7 14 9
21 1 16
45 1 7
222 5 17 10 6 1 3
12 15 13 16 9 17 6 4 18 10 1 14 19
11
43 9 61 10 33 57 51 72 49 69 95
29
200 4 8 3 5 9
11 4 2 1 7 11
36 2 7 2
57 2 9 5
78 2 9 2
20 4 1 7 5 6
107 3 11 9 3
4 3 8 6 11
1 2 6 10
25 4 11 6 10 7
99 5 1 7 3 10 5
236 5 8 6 3 9 4
76 2 3 2
95 4 9 6 1 8
74 4 11 7 3 8
170 4 10 1 5 3
79 3 9 1 7
32 1 7
91 3 11 3 8
163 4 10 3 9 11
99 5 4 2 9 7 8
209 5 3 6 10 9 11
182 4 2 11 1 3
91 2 4 3
28 1 5
143 4 8 1 10 9
22 1 11
25 1 5
14 2 4 11
5 7 8 10 1 4
16
31 65 17 70 28 16 67 27 86 97 6 63 72 71 46 26
22
23 2 13 6
3 2 15 14
222 5 14 8 10 4 6
16 1 13
33 1 14
165 7 12 9 1 11 7 13 6
33 3 2 5 12
106 4 1 14 9 15
130 3 6 4 16
78 2 15 13
93 3 6 5 10
3 2 5 2
295 8 14 2 15 13 4 8 3 12
9 3 9 11 2
22 1 9
227 7 8 6 12 7 1 14 4
34 1 5
132 3 8 2 10
41 1 4
95 2 15 1
92 5 5 6 4 14 8
7 1 9
15 5 3 13 4 16 8 10 6 7 2 14 15 9 12 1
15
96 5 67 21 87 5 37 17 93 42 50 53 58 47 81
22
6 1 2
100 5 1 9 11 13 5
226 5 12 6 4 9 3
96 2 8 2
254 6 14 6 12 10 5 15
210 6 13 15 11 2 7 4
28 3 8 12 10
31 3 1 5 11
24 1 12
37 1 3
194 6 15 12 8 11 6 4
207 7 10 9 7 1 12 11 6
248 6 4 7 10 6 9 2
51 4 15 9 2 1
7 3 14 7 13
258 7 14 10 15 11 7 6 13
47 3 8 1 13
47 3 3 8 5
96 4 7 5 1 12
77 2 8 10
13 4 7 15 8 6
63 5 5 2 11 6 14
9 2 8 15 9 6 5 10 1 14
12
5 1 51 19 97 13 74 51 57 29 92 47
22
27 3 3 9 2
27 1 4
258 6 8 6 3 9 1 10
32 6 8 4 9 3 1 5
178 4 11 6 8 7
30 2 11 2
188 5 9 2 8 7 3
160 4 12 9 7 10
2 1 7
33 1 5
130 5 1 2 6 10 7
43 2 5 7
45 5 7 6 9 8 3
86 2 2 4
86 2 1 10
33 1 9
48 1 6
23 3 12 7 5
167 6 10 4 1 6 11 5
69 6 2 11 6 3 9 8
54 2 1 9
124 3 5 7 3
7 5 11 12 10 1 6 3
13
56 43 99 36 77 59 50 53 21 34 67 16 84
6
64 2 12 11
76 4 1 10 13 4
268 6 10 11 4 13 1 8
242 6 7 11 6 1 5 13
88 2 6 4
268 6 2 3 6 4 13 10
9 2 9 6 7 10 8 11 3 1
16
19 31 19 46 23 88 60 20 13 80 19 85 71 12 71 87
10
48 1 6
253 6 8 3 11 12 14 9
37 1 9
16 1 2
42 6 8 16 1 13 10 2
309 8 8 12 11 10 13 15 5 1
146 3 2 3 6
39 1 4
5 2 2 10
42 4 8 6 2 1
11 2 3 13 1 8 9 7 11 14 5 15
12
95 67 33 90 5 94 72 3 63 60 79 18
27
224 5 2 11 8 3 10
64 5 8 5 6 1 10
121 4 3 4 11 1
134 5 2 11 1 7 3
79 5 7 9 12 8 5
34 1 12
12 1 9
111 5 8 3 12 7 4
39 1 9
44 4 9 8 1 11
120 4 2 6 11 10
36 6 4 9 7 2 10 1
96 2 7 6
131 4 10 4 6 12
14 2 3 5
28 3 5 6 9
22 5 9 12 5 6 7
137 5 11 12 9 2 7
39 4 5 4 2 7
50 3 4 5 3
49 4 7 12 8 2
83 2 8 4
118 3 9 5 4
143 5 12 11 3 1 2
132 5 5 6 10 9 1
120 5 11 1 3 7 10
46 1 8
7 10 3 4 2 12 9 6
14
92 81 27 38 74 84 74 80 69 12 90 97 24 20
11
139 4 5 13 1 10
71 5 5 1 11 3 14
72 3 4 8 12
215 4 9 10 2 6
45 1 2
54 5 13 1 4 10 12
101 4 2 14 9 10
82 2 12 3
262 7 8 2 14 1 4 11 9
158 5 11 12 2 9 14
52 4 8 12 14 7
13 11 8 9 12 5 7 14 2 13 3 6 10 1
13
35 33 87 28 86 34 80 40 14 17 37 31 21
7
268 6 8 10 13 9 7 2
92 2 10 2
27 1 6
19 2 10 13
7 1 7
135 3 7 11 6
90 5 1 8 10 9 6
9 12 6 2 10 7 5 11 8 13
20
50 42 21 81 91 9 83 96 39 33 46 12 75 21 65 62 7 58 39 55
13
310 7 3 17 5 10 13 7 16
321 7 13 20 16 18 5 15 4
125 5 3 2 14 18 1
201 6 6 2 3 9 16 7
27 1 9
403 10 18 14 9 15 3 17 4 11 13 10
196 4 20 3 10 15
45 10 19 15 7 4 13 9 14 8 18 16
152 10 5 20 2 8 17 13 6 9 12 16
6 6 17 13 19 10 1 5
47 1 7
182 4 15 12 9 19
255 5 18 14 3 5 4
12 6 12 3 5 10 16 11 7 9 2 20 4