Dao cot
Ann
c_cpp
2 years ago
21 kB
5
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
#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 0Editor is loading...