Untitled
unknown
plain_text
a year ago
23 kB
4
Indexable
Đảo Cột
Trong ma trận nhị phân, phép đảo cột của ma trận là việc thay thế các giá trị của cột
đó từ 0 -> 1 và từ 1 -> 0. Cho ma trận nhị phân NxM (N <= 100, M <= 20), hỏi sau K
lần đảo cột thì số hàng gồm toàn số 1 nhiều nhất có thể thu được là bao nhiêu. (Yêu
cầu phải đảo cột đúng K lần và một cột có thể được đảo nhiều lần)
Ví dụ
Với ví dụ bên, nếu K = 1, ta sẽ có kết quả lớn nhất khi đảo cột thứ 2 và thu được 1
hàng gồm toàn số 1 là hàng thứ 4. Nếu K = 2, kết quả thu được là 2 khi đảo cột thứ 2
và cột thứ 3.
0
1
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
1
1
1
1
0
0
1
1
K=1, có 1 hàng toàn 1
0
0
0
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
1
1
1
1
0
1
1
K=2, có 2 hàng toàn 1
0
0
1
0
0
1
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
1
1
1
1
Input: Cho 3 số N, M, K
Tiếp theo là ma trận NxM
Output: In ra số lượng hàng toàn 1 nhiều nhất định dạng như bên dưới
Case #1 1
Case #2 2
//Input
10
5 5 1
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
1 0 1 1 1
1 0 0 1 1
5 5 2
0 1 0 0 0
1 0 0 1 1
0 0 0 0 0
1 0 1 1 1
1 0 0 1 1
50 10 21
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
0 0 1 1 0 1 1 1 0 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1 0
1 0 1 0 1 1 0 0 1 1
1 0 1 0 1 1 0 0 1 1
1 0 1 0 1 1 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 1 1 1 0 0 0 0 1
0 0 1 1 1 0 0 0 0 1
50 10 49
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
0 1 1 0 1 0 0 1 0 0
1 0 0 1 1 0 1 1 0 0
1 0 0 1 1 0 1 1 0 0
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 0 0 0 0 0 0 1
0 0 1 1 1 1 1 1 0 0
1 0 0 1 0 1 1 0 0 1
0 1 0 0 0 1 1 1 0 1
50 10 31
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 0 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 0 1 1 1
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 1 0 0 1 0 0 1 0
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
1 1 0 0 0 1 1 0 1 1
0 0 0 0 0 1 0 1 1 1
50 10 46
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
1 0 1 0 0 1 1 0 1 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1 0 1
0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 1 0 1
1 0 1 0 1 1 0 0 0 0
1 0 1 0 1 1 0 0 0 0
1 0 1 0 1 1 0 0 0 0
1 0 1 0 1 1 0 0 0 0
1 0 1 0 1 1 0 0 0 0
1 0 1 0 1 1 0 0 0 0
1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0 1 1
50 10 39
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
1 1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1 1
1 1 1 1 0 0 0 1 1 1
1 0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 1 0 0 0
1 0 0 1 1 1 0 0 1 1
1 0 0 1 1 1 0 0 1 1
0 0 1 0 1 0 0 0 1 0
0 0 1 0 1 0 0 0 1 0
1 0 0 1 0 0 0 1 1 0
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 1 0 0 0 1
100 20 10
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0
1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0
1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0
0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1
0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1
0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1
0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1
1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1
0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
1 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1
0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 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 0 1 1 1 0 1 1 0 0 1 1 1 0 0 1 0
100 20 3560
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100 20 9928
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// Solution:
package Lesson_17;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Dao_Cot {
static int T, N, M, K;
static int board[][], newBoard[][];
static int max;
public static void turnColumn(int column){
for(int i = 0; i < N; i++){
if(board[i][column] == 1)
board[i][column] = 0;
else
board[i][column] = 1;
}
}
public static boolean checkOneRow(int row){
for(int i = 0; i < M; i++){
if(board[row][i] != 1) return false;
}
return true;
}
public static void mergeRow(){
int index = 0;
for(int r = 0; r < N; r++){
for(int c = 0; c < M; c++){
if(board[r][c] != board[r+1][c]){
index++;
continue;
}
}
for(int c = 0; c < M; c++){
newBoard[index][c] = board[r][c];
}
}
}
public static void backTrack(int column, int sumRowOne, int k){
if(column >= M) return;
if(k == K){
for(int i = 0; i < N; i++){
if(checkOneRow(i)) sumRowOne++;
}
if(max < sumRowOne) max = sumRowOne;
return;
}
// Check lat tai 1 cot
if((K-k)%2 == 0)
backTrack(column, sumRowOne, K);
else{
turnColumn(column);
backTrack(column, sumRowOne, K);
turnColumn(column);
}
turnColumn(column);
backTrack(column+1, sumRowOne, k+1);
turnColumn(column);
backTrack(column+1, sumRowOne, k);
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Dao_Cot"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
M = scanner.nextInt();
K = scanner.nextInt();
board = new int[N][M];
newBoard = new int[N][M];
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
board[i][j] = scanner.nextInt();
}
}
max = -1;
backTrack(0, 0, 0);
System.out.println("Case #" + tc + " "+ max);
}
}
}
// Quan Hau
Quân Hậu
Cho bàn cờ có kích thước NxN, và N quân hâu.
Có bao nhiêu cách để sắp xếp N quân hâu vào bàn cờ sao cho chúng không đe dọa lẫn nhau
input:
Dòng đầu tiên là số lương testcase,
Các dòng tiếp theo là kích thước bàn cờ N cho mỗi testcase.
Output:
In ra mỗi testcase với kết quả là số cách sắp xếp dưới dạng:
Case #1: 1
Case #2: 0
Case #3: 0
13
1
2
3
4
5
8
6
7
13
12
11
9
10
package Lesson_17;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Quan_Hau {
static int N, T;
static int row[], sumSolution;
public static boolean checkValid(int r, int c){
for(int i = 0; i < r; i++){
if(c == row[i] || (r - i) == (row[i] - c )
|| (r- i) == (c - row[i])) return false;
}
return true;
}
public static void backTrack(int k){
if(k == N){
sumSolution++;
}
for(int i = 0; i < N; i++){
if(checkValid(k, i)){
row[k] = i;
backTrack(k+1);
}
}
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Queen"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
N = scanner.nextInt();
row = new int[N];
sumSolution = 0;
backTrack(0);
System.out.println("Case #"+ tc + ": " + sumSolution);
}
}
}
Leave a Comment