Painting
quoc14
c_cpp
15 days ago
32 kB
5
Indexable
Never
Backtrack
Level 4
Painting
Nhóm thiết kế tại SAMSUNG Electronics đang cân nhắc một thiết kế sáng tạo cho sản phẩm mới.
Hình bên trái là sơ đồ cơ bản và nhóm thiết kế cố gắng phân biệt từng khu vực được đánh dấu bằng chữ cái trong bảng chữ cái bằng bốn màu.
Khi tiến hành, nhóm thiết kế theo đuổi sự hoàn hảo bằng cách nghiên cứu sự kết hợp của tất cả các màu sắc và chọn một trong số chúng.
Tuy nhiên, họ gặp khó khăn vì không biết tổng số trường hợp kết hợp màu sắc.
Do khó khăn này, bạn chuyển đổi sơ đồ cơ bản bên trái thành đồ thị ở giữa, sau đó giải quyết vấn đề bằng cách chuyển đổi nó thành ma trận kề bên phải.
Số ca bệnh là 264.
Phương pháp nào được sử dụng để giải quyết vấn đề này? (Thời gian giới hạn: 2 giây)
[Đầu vào]
Ma trận kề xung quanh một sơ đồ cơ bản được nhập vào.
Dòng đầu tiên ghi số lượng các trường hợp thử nghiệm (1<=T <= 10).
Dòng đầu tiên của mỗi trường hợp thử nghiệm là kích thước của ma trận n (1<= n <= 30, n là số dương).
Từ dòng thứ hai, các giá trị của ma trận được nhập bằng cách phân biệt một ô trống hoặc ô trống khác.
[Đầu ra]
Đối với mỗi trường hợp thử nghiệm, bạn nên in "Trường hợp #T" ở dòng đầu tiên trong đó T có nghĩa là số trường hợp.
Ở dòng thứ hai, in ra tổng số trường hợp cần tô màu và phân biệt chúng bằng bốn màu cho mỗi khu vực.
[Sample Input ]
3
4
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0
5
0 1 1 1 0
1 0 0 1 1
1 0 0 1 0
1 1 1 0 1
0 1 0 1 0
7
0 1 0 0 1 0 1
1 0 1 0 1 0 0
0 1 0 1 1 0 0
0 0 1 0 1 1 0
1 1 1 1 0 1 1
0 0 0 1 1 0 1
1 0 0 0 1 1 0
[Sample Output]
Case #1
108
Case #2
96
Case #3
264
Case #1
864
Case #2
1152
Case #3
96
Case #4
96
Case #5
1152
Case #6
576
Case #7
2496
Case #8
384
Case #9
96
Case #10
5280
Case #11
384
Case #12
2688
Case #13
384
Case #14
5760
Case #15
2112
Case #16
384
Case #17
9792
Case #18
2304
Case #19
2208
Case #20
192
Case #21
1536
Case #22
576
Case #23
768
Case #24
192
Case #25
1152
Case #26
2784
Case #27
192
Case #28
1440
Case #29
192
Case #30
14208
Case #31
96
Case #32
192
Case #33
384
Case #34
3840
Case #35
192
Case #36
192
Case #37
768
Case #38
1152
Case #39
192
Case #40
1152
Case #41
480
Case #42
10368
Case #43
288
Case #44
288
Case #45
96
Case #46
384
Case #47
192
Case #48
96
Case #49
576
Case #50
192
Time: 0.687000000 s.
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
#include <iostream>
#include <time.h>
using namespace std;
int oo = 2000000000;
int T, n, mp[31][31], result, vs[31];
int color[31][4];
bool check(int index, int c){
for(int i = 0; i < n; i++){
if(mp[index][i] && color[i][c]) return false;
}
return true;
}
void backtrack(int index){
if(index == n){
result++;
return;
}
for(int i = 0; i < 4; i++){
if(check(index, i)){
color[index][i]++;
backtrack(index + 1);
color[index][i]--;
}
}
}
int main(){
freopen("input.txt", "r", stdin);
// Calc clock
clock_t time_start, time_end;
time_start = clock();
cin >> T;
for(int tc = 1; tc <= T; tc++){
// Initial && Input
result = 0;
cin >> n;
for(int i = 0; i < n; i++){
vs[i] = 0;
for(int j = 0; j < n; j++) cin >> mp[i][j];
for(int j = 0; j < 4; j++) color[i][j] = 0;
}
// Solve Problem
backtrack(0);
// Output
cout << "Case #" << tc << endl << result << endl;
}
// Calc Time
time_end = clock();
cout.setf(ios::fixed);
cout.precision(9);
cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
return 0;
}Leave a Comment