Dao cot

 avatar
Ann
c_cpp
a year ago
21 kB
0
Indexable
Never
Đả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

#include<iostream>

using namespace std;

int n,m,k,ans;
int a[105][25];
int visited[105];
int b[105][25];
void reset_array(){
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			a[i][j] = b[i][j];
	}
}

void reset_visit(){
	for (int i = 0; i < n; i++)
		visited[i] = 0;
}

void dao_cot(int j){
	for (int i = 0; i < n; i++)
		a[i][j] = 1 - a[i][j];
}

int dem_so_0(int i){
	int count = 0;
	for (int j = 0; j < m; j++)
	{
		if(a[i][j] == 0){
			count++;
		}
	}
	return count;
}

int dem_so_hang_1(){
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		bool flag = true;
		for (int j = 0; j < m; j++)
		{
			if(a[i][j] == 0) flag = false;
		}
		if(flag) count++;
	}
	return count;
}

int main(){
	//freopen("input.txt","r",stdin);
	int t; cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin >> n >> m >> k;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> a[i][j];
				b[i][j] = a[i][j];
			}
		}
		ans = 0;
		for (int i = 0; i < n; i++)
		{
			visited[i] = 1;
			int x = dem_so_0(i);
			if(x <= k && (k - x) % 2 == 0){
				for (int j = 0; j < m; j++)
				{
					if(a[i][j] == 0){
						dao_cot(j);
					}
				}
				int u = dem_so_hang_1();
				if(u > ans) ans = u;
			}
			reset_array();
		}
		reset_visit();
		cout << "Case #" << tc << " " << ans << endl;
	}
	return 0;
}



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