GCJ Round1A Charging Chaos
Problem
Shota the farmer has a problem. He has just moved into his newly built farmhouse, but it turns out that the outlets haven't been configured correctly for all of his devices. Being a modern farmer, Shota owns a large number of smartphones and laptops, and even owns a tablet for his favorite cow Wagyu to use. In total, he owns N different devices.
As these devices have different specifications and are made by a variety of companies, they each require a different electric flow to charge. Similarly, each outlet in the house outputs a specific electric flow. An electric flow can be represented by a string of 0s and 1s of length L.
Shota would like to be able to charge all N of his devices at the same time. Coincidentally, there are exactly N outlets in his new house. In order to configure the electric flow from the outlets, there is a master control panel with L switches. The ithswitch flips the ith bit of the electric flow from each outlet in the house. For example, if the electric flow from the outlets is:
Then flipping the second switch will reconfigure the electric flow to:
If Shota has a smartphone that needs flow "11"to charge, a tablet that needs flow "10"to charge, and a laptop that needs flow "00"to charge, then flipping the second switch will make him very happy!
Misaki has been hired by Shota to help him solve this problem. She has measured the electric flows from the outlets in the house, and noticed that they are all different. Decide if it is possible for Shota to charge all of his devices at the same time, and if it is possible, figure out the minimum number of switches that needs to be flipped, because the switches are big and heavy and Misaki doesn't want to flip more than what she needs to.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three lines. The first line contains two space-separated integers N and L. The second line contains N space-separated strings of length L, representing the initial electric flow from the outlets. The third line also contains N space-separated strings of length L, representing the electric flow required by Shota's devices.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of switches to be flipped in order for Shota to charge all his devices. If it is impossible, y should be the string "NOT POSSIBLE"(without the quotes). Please note that our judge is not case-sensitive, but it is strict in other ways: so although "not possible"will be judged correct, any misspelling will be judged wrong. We suggest coping/pasting the string NOT POSSIBLE into your code.
Limits
1 ≤ T ≤ 100. No two outlets will be producing the same electric flow, initially. No two devices will require the same electric flow.
Small dataset
1 ≤ N ≤ 10. 2 ≤ L ≤ 10.
Large dataset
1 ≤ N ≤ 150. 10 ≤ L ≤ 40.
Sample
Input
Output
Explanation
In the first example case, Misaki can flip the second switch once. The electric flow from the outlets becomes:
Then Shota can use the outlet 0 to charge device 1, the outlet 1 to charge device 2, outlet 2 to charge device 0. This is also a solution that requires the minimum amount number of switches to be flipped.
今度の試合に参加して、自信がショックを受けそうになりました.の第1ラウンドの最初の問題の小さなデータさえこんなに手間がかかります.のこの問題のビッグデータはさらに何の見当もつかない.のコードを叩くのに30分もたたないうちに、デバッグ+最終的に通過するのに1時間半もかかりました.期間WAは5回..やはり練習が少ないですね.いろいろな手が不自由です.のコンセントとプラグを合わせて、同じ时に差し込むことができます.少なくとも何本かの线の电流を変えて差し込むことができます.私はBFSで作ったのです.コードは次のとおりです.
Shota the farmer has a problem. He has just moved into his newly built farmhouse, but it turns out that the outlets haven't been configured correctly for all of his devices. Being a modern farmer, Shota owns a large number of smartphones and laptops, and even owns a tablet for his favorite cow Wagyu to use. In total, he owns N different devices.
As these devices have different specifications and are made by a variety of companies, they each require a different electric flow to charge. Similarly, each outlet in the house outputs a specific electric flow. An electric flow can be represented by a string of 0s and 1s of length L.
Shota would like to be able to charge all N of his devices at the same time. Coincidentally, there are exactly N outlets in his new house. In order to configure the electric flow from the outlets, there is a master control panel with L switches. The ithswitch flips the ith bit of the electric flow from each outlet in the house. For example, if the electric flow from the outlets is:
Outlet 0: 10
Outlet 1: 01
Outlet 2: 11
Then flipping the second switch will reconfigure the electric flow to:
Outlet 0: 11
Outlet 1: 00
Outlet 2: 10
If Shota has a smartphone that needs flow "11"to charge, a tablet that needs flow "10"to charge, and a laptop that needs flow "00"to charge, then flipping the second switch will make him very happy!
Misaki has been hired by Shota to help him solve this problem. She has measured the electric flows from the outlets in the house, and noticed that they are all different. Decide if it is possible for Shota to charge all of his devices at the same time, and if it is possible, figure out the minimum number of switches that needs to be flipped, because the switches are big and heavy and Misaki doesn't want to flip more than what she needs to.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three lines. The first line contains two space-separated integers N and L. The second line contains N space-separated strings of length L, representing the initial electric flow from the outlets. The third line also contains N space-separated strings of length L, representing the electric flow required by Shota's devices.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum number of switches to be flipped in order for Shota to charge all his devices. If it is impossible, y should be the string "NOT POSSIBLE"(without the quotes). Please note that our judge is not case-sensitive, but it is strict in other ways: so although "not possible"will be judged correct, any misspelling will be judged wrong. We suggest coping/pasting the string NOT POSSIBLE into your code.
Limits
1 ≤ T ≤ 100. No two outlets will be producing the same electric flow, initially. No two devices will require the same electric flow.
Small dataset
1 ≤ N ≤ 10. 2 ≤ L ≤ 10.
Large dataset
1 ≤ N ≤ 150. 10 ≤ L ≤ 40.
Sample
Input
Output
3
3 2
01 11 10
11 00 10
2 3
101 111
010 001
2 2
01 10
10 01
Case #1: 1
Case #2: NOT POSSIBLE
Case #3: 0
Explanation
In the first example case, Misaki can flip the second switch once. The electric flow from the outlets becomes:
Outlet 0: 00
Outlet 1: 10
Outlet 2: 11
Then Shota can use the outlet 0 to charge device 1, the outlet 1 to charge device 2, outlet 2 to charge device 0. This is also a solution that requires the minimum amount number of switches to be flipped.
今度の試合に参加して、自信がショックを受けそうになりました.の第1ラウンドの最初の問題の小さなデータさえこんなに手間がかかります.のこの問題のビッグデータはさらに何の見当もつかない.のコードを叩くのに30分もたたないうちに、デバッグ+最終的に通過するのに1時間半もかかりました.期間WAは5回..やはり練習が少ないですね.いろいろな手が不自由です.のコンセントとプラグを合わせて、同じ时に差し込むことができます.少なくとも何本かの线の电流を変えて差し込むことができます.私はBFSで作ったのです.コードは次のとおりです.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include<algorithm>
using namespace std;
int n, m, s1[20][20], s2[20][20];
struct node
{
int a[20][20];
int ans, x;
} q[1000000];
void bfs()
{
int i, j, s=0, e=0, k, x, y, z;
node f1, f2;
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
f1.a[i][j]=s1[i][j];
}
}
f1.ans=0;
f1.x=-1;
q[s++]=f1;
while(s>e)
{
f1=q[e++];
/*for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%d ",f1.a[i][j]);
}
printf("
");
}*/
x=0;
for(i=0; i<n; i++)
{
y=0;
for(j=0; j<n; j++)
{
z=0;
for(k=0; k<m; k++)
{
if(f1.a[i][k]!=s2[j][k])
{
z=1;
break;
}
}
if(z==0)
{
y=1;
break;
}
}
if(y==0)
{
x=1;
break;
}
}
if(x==0)
{
/*for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%d ",f1.a[i][j]);
}
printf("
");
}*/
printf("%d
",f1.ans);
return ;
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
f2.a[i][j]=f1.a[i][j];
}
}
if(f1.x<m)
{
f2.x=f1.x+1;
f2.ans=f1.ans;
q[s++]=f2;
}
for(i=f1.x+1; i<m; i++)
{
for(int i1=0; i1<n; i1++)
{
for(int j1=0; j1<m; j1++)
{
f2.a[i1][j1]=f1.a[i1][j1];
}
}
for(j=0; j<n; j++)
{
f2.a[j][i]=1-f1.a[j][i];
}
f2.ans=f1.ans+1;
f2.x=i;
q[s++]=f2;
}
}
printf("NOT POSSIBLE
");
return ;
}
int main()
{
int t, i, j, num=0;
char s[20];
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
scanf("%d",&t);
while(t--)
{
num++;
scanf("%d%d ",&n,&m);
for(i=0; i<n; i++)
{
scanf("%s",s);
for(j=0; j<m; j++)
s1[i][j]=s[j]-'0';
}
for(i=0; i<n; i++)
{
scanf("%s",s);
for(j=0; j<m; j++)
s2[i][j]=s[j]-'0';
}
printf("Case #%d: ",num);
bfs();
}
return 0;
}