fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6. string a;
  7. int res;
  8. };
  9.  
  10. int main() {
  11. // your code goes here
  12. int t;
  13. cin>>t;
  14.  
  15. for(int te=1;te<=t;te++)
  16. {
  17. int n,l,flag=0;
  18. cin>>n>>l;
  19.  
  20. bool vis[n];
  21. memset(vis,false,sizeof(vis));
  22.  
  23. string a,initial,final;
  24. for(int tr=0;tr<n;tr++)
  25. {
  26. cin>>a;
  27. initial+=a;
  28. }
  29. for(int tr=0;tr<n;tr++)
  30. {
  31. cin>>a;
  32. final+=a;
  33. }
  34. queue<node> q;
  35. node x;
  36. x.a = initial;
  37. x.res=0;
  38. q.push(x);
  39. set<string> s;
  40.  
  41. while(!q.empty())
  42. {
  43. node u = q.front();
  44. q.pop();
  45. int count=0;
  46. for(int i=0;i<u.a.size();i+=l)
  47. {
  48. string temp = u.a.substr(i,l);
  49. for(int j=0;j<final.size();j+=l)
  50. {
  51. if(temp==final.substr(j,l)&&!vis[j])
  52. {
  53. vis[j]==true;
  54. count++;
  55. break;
  56. }
  57. }
  58. if(count==n)
  59. {
  60. cout<<"Case #"<<te<<':'<<" "<<u.res<<endl;
  61. flag=1;
  62. break;
  63. }
  64. }
  65. if(flag)
  66. break;
  67.  
  68. for(int i=0;i<l;i++)
  69. {
  70. node v = u;
  71. for(int j=i;j<u.a.size();j+=l)
  72. {
  73. if(v.a[j]=='1')
  74. v.a[j]='0';
  75. else
  76. v.a[j]='1';
  77. }
  78. v.res++;
  79. if(s.count(v.a))
  80. continue;
  81. q.push(v);
  82. s.insert(v.a);
  83. //cout<<v.a<<endl;
  84. }
  85. }
  86. if(flag==1)
  87. continue;
  88. cout<<"Case #"<<te<<":"<<" NOT POSSIBLE"<<endl;
  89. }
  90. return 0;
  91. }
Success #stdin #stdout 0.21s 5284KB
stdin
100
1 2
00
01
8 5
11110 11000 00001 11111 10111 11001 01111 11101
11011 11100 10000 10011 10111 01000 00101 10010
5 4
0101 0000 0111 1111 0110
0101 0110 1100 0100 0011
8 9
110111000 100110000 100110111 110111111 010011000 000010000 010111001 000110001
110101101 110001100 100100101 100000100 000000010 010001010 000000101 010001101
4 9
101101111 100000111 010111001 100111100
110111100 011111111 011111110 010010000
10 9
111010111 101101111 010000100 000101110 101110010 100011001 111000011 101000110 110000010 111000001
011101011 110101110 110101100 111101101 100011101 001000001 100000000 100101001 101110110 110111000
4 8
11000001 11001001 10000010 10001010
11011010 10011001 11010010 10010001
10 9
000110101 111100010 000111000 010001001 000000100 111011101 111011100 011110010 111111001 011100010
000000001 001010100 011100010 111001011 011011011 100000000 100011010 101110101 000010000 010011111
1 10
0011111110
1100000000
9 9
000100111 010101101 110001101 010111000 010000000 010010011 110110010 011100101 110110110
011001111 000001111 000101010 110001110 010101011 111100100 111110101 001001100 110000011
2 9
111001111 110000000
110000000 111001111
4 9
110010011 000000100 000001010 101000011
111110011 000000100 011101111 011000011
1 6
110001
010011
10 10
0111010010 1111111011 1000011100 1111110010 0001001101 0100100101 0110000010 1000100001 0000011101 1011101110
0010101111 1011000011 0101111100 1010010011 1101011100 0001100000 0010010010 0101110101 1110101011 1100001100
10 6
101010 011011 001101 111001 000101 100110 110110 011000 100000 111101
011100 011111 001001 110010 101110 111001 100100 100010 111101 000001
10 10
1101011111 0101110001 0010001001 1010110000 1011001010 0010111111 1100000101 1101100110 0100110010 0011001100
1001110110 1111001101 1000110011 0110011001 0111111010 0110100000 1001000000 0001001111 1110001110 0000110101
10 10
0010000001 1000011101 1001100111 0101100001 1110010110 0000110110 0111001010 1101111000 1010011111 0111101000
1101110101 1000100010 1111011110 0001110011 0000001001 1010010101 1111111100 0010001011 0101101100 0110000010
10 10
1000000000 0010110000 1001011101 0111000000 1100001000 1111101100 1110111101 1010100110 1010010101 0100001100
1100111101 1000100110 1000010101 1101101100 0000110000 0101000000 1011011101 1010000000 0110001100 1110001000
10 10
0001101101 1010000010 1110010001 0001111111 0011101011 1100100100 1010011110 1110100000 0101011010 0101010101
1100011011 0011001100 1010100101 0111101110 0111011111 1000100011 1000110001 0101101010 1100010100 0011010000
4 6
110110 011101 100110 001101
001101 100110 011101 110110
2 9
011101011 100000110
100000100 011101001
1 6
010011
001000
10 10
0101001110 0001010110 1110100000 1010111011 0100110101 0011001110 0100010001 1001101001 1110110001 1011001110
0111110011 1111001100 0000101011 1010101111 0100100001 0000111010 1011010100 0101010100 1101010100 1010001011
10 10
0110000011 1000110000 1111110101 1011011010 0100001000 1000101111 1111001100 0001101101 0010110110 0101010011
0101100001 1010110011 0111101010 1001011001 0100111010 0000000100 1110011100 1001000110 0011011111 1110100101
6 9
001001000 110100000 011101111 011101000 100000000 110100111
001011000 011111000 100010000 100010111 110110000 001011111
10 10
1000000000 0011011000 0010010101 0100111101 1101111110 0101101010 1010100110 1011001011 1100110101 0111000011
0101001011 1010001000 1001110110 1110010011 1000100001 0000110101 1111011110 0001111110 0111101101 0110000000
6 5
00000 01001 10101 11000 01111 01100
00011 00000 10100 01010 01001 10110
10 10
0011010110 0000100000 0000111101 1111011111 1000100011 0101101001 0111011000 1111010110 1010101000 1100000111
1101110000 0111000110 1010001100 1110101000 0001111001 0010010010 1101111001 1000000111 0010001111 0101110111
1 6
001110
010001
6 6
111111 011110 110001 101111 101000 001000
101101 110011 111101 011100 101010 001010
2 7
1000110 1110100
1011010 0000011
6 10
0001000001 0001011011 1111111110 0101010101 1011010000 0101010000
0111100001 0101110001 1011001001 1010010100 0010000101 1101000000
7 6
001011 000101 010110 110001 010101 010000 000100
110010 100010 100111 111100 000110 110011 100001
8 5
11010 11110 10110 00111 10001 10010 10101 00011
10010 01011 00100 00000 10110 00011 01111 00111
8 7
1100000 1011101 1010110 0111011 0011011 0111000 1001001 1001000
1110100 1000010 1111111 1101010 0111001 0011001 0011010 1101011
1 6
110001
101000
5 5
11110 00010 00101 01111 10110
01001 00001 01111 10111 11111
1 3
011
100
4 8
10100100 00100011 01111110 00100010
11110110 01110001 11110111 10101011
8 10
1100111100 0111011100 0110101000 0110011000 1101111011 1001101000 1010010111 0011011011
1001100001 1101110010 1100110101 0011010010 0110010001 1010011110 0110100001 0111010101
10 10
0100100100 0010000010 1100110110 0000010101 0001111001 1100101100 1011110010 0111001111 1111001011 1011011001
1111001001 1111100010 1000001101 0110111001 0100101110 0011110100 0101000010 0000011111 1000010111 1011110000
2 2
01 00
11 10
1 5
01111
00000
6 6
011111 011010 100111 011101 011001 000110
101100 101000 111010 001111 100101 000111
8 7
0010011 0000011 0000001 1011000 1001010 1010000 1011101 0101100
0101011 0110010 0011001 0100111 1000110 0110111 1101100 0010101
10 10
1100011100 1110100110 0110000011 1100010100 1001110000 0101101001 0011101011 0001110011 1010001111 0011011100
0011000010 0011001010 1100000010 0101010001 1110101101 1100110101 1001011101 0110101110 0001111000 1010110111
6 6
000010 111001 011101 100010 011001 000110
011101 111101 100110 000110 111001 100010
5 8
10011011 00011100 01100111 00001001 01010100
01111000 00000011 01101101 11111111 00110000
10 10
0110111100 0101010101 1000000011 0001111111 0110101111 1010000000 0110010000 1011110011 1101101010 1001001100
1001000000 1001101100 0110110000 1010101001 0100001111 0010010110 0101111100 1110000011 0111111111 1001010011
4 4
0000 0110 1000 1110
1101 1011 0011 0101
10 10
1010101111 0101011111 0101000000 1101110011 1000101100 0010000101 1110111001 0010111100 1111010010 0001000010
1100111010 0000000110 1010101111 1000101100 0111000011 1101010001 1111110000 0000111111 0011000001 0111011100
10 10
0010000100 0001100010 0001110001 1010011000 0100111101 0100001110 1110000111 1101101110 1111011001 1011110011
0011010001 0011100010 0110111101 0101011011 1010110001 1000000110 1001011000 1100101100 0110101110 1101000111
2 6
111001 011011
000011 100001
10 10
1011010100 1100101000 0101010011 1100010000 1001100001 1101011101 0010101110 0010111111 0011100011 0110001110
0110010000 0001010100 0011100001 1000101110 1001100011 1000111111 1100001110 0110101000 0111011101 1111010011
10 10
0111001001 0101011100 1110001101 0001100111 1000100011 0001111010 1000110110 1010010000 1110101001 0111010110
0110111001 1111100010 1001010011 0110011101 0000000010 1001001110 0000010111 1101101000 1111111101 0010100100
6 8
01010110 01011110 01111101 01110101 10100111 10101111
11110101 11111101 00101111 11011110 11010110 00100111
10 10
0101110101 1010010000 0100111111 1111001000 0001110111 1000001100 1010001010 0101100001 0011011010 1110100111
0111111101 0011001010 0011010000 1100111011 1101100101 0110010010 1000101101 0001010110 1010000000 1100101111
10 10
1011110110 0101000110 1010010100 0011001000 1100101011 1101011001 1100100010 0110111101 0010100111 0001011001
1101000010 1000110111 0110100110 0001101011 1010100110 1110111001 0000001001 0111010100 1001011000 0111011101
10 10
1000110011 0010010011 1100011100 0110100011 0010100001 0101001100 0001001110 1101111000 1011000111 1111111100
0110011111 1110101011 1010101001 0000100000 0100011011 1001000110 0011010100 0111111011 1101000100 1001110100
5 5
00101 10110 11101 01101 00010
10101 00001 11010 01010 10010
4 8
01100011 10011010 10010010 01101011
01100011 01101011 10011010 10010010
5 10
0100010100 1111100101 1010110111 1100001101 1011111011
1101101101 1110000101 0101110100 1010011011 1011010111
10 10
1100001101 1101110111 0011100001 0010000110 1100111010 1000101000 0011011010 0110011100 1001010011 0111100101
0001011011 0100000100 1010101001 1110010110 1010010010 0101111110 1011110101 0101001001 1111101111 0000100000
6 4
1111 0111 1110 0010 0011 0110
0111 1110 1010 1111 1011 0110
10 10
0010010101 1100011011 0110001011 1100100100 1000100010 1101101010 0011110111 0011001000 0001111100 1111010101
1001011010 0111101011 0011101101 1101000100 1000111000 1010110011 0110100101 0100011010 0111010100 1000000111
10 10
0000111100 0110001000 1011101111 1100010011 0101010100 1011000100 0110100110 1000001011 1111110011 0001111001
1011101110 0001011011 0111000001 1111110110 1100010010 1100111001 0010101001 0001110101 0110000100 1000001110
10 10
1111001000 0001111000 0001110111 1010010001 0000001000 1001101111 0100000111 0110110110 1110011000 1111100111
0011011010 1100110101 0100011011 1101001010 1101100101 0110101010 1000111100 0011010101 1011000010 0010100101
1 9
101000100
010100101
10 10
0011000101 1010101000 0100111100 1101110011 1000100110 0101011111 0111101001 0010011010 1100010101 1011000010
1101111011 0011001101 0101111100 0110011000 1010000010 0100010110 1011100001 1001010111 0010101011 1100100100
10 6
010101 000100 101100 111011 000111 100101 101010 101000 010000 010110
001011 010100 111000 101110 010000 010101 100001 001110 000101 000001
10 10
0101001111 0001011010 0100101110 0010010100 1011110001 1111011011 1001100000 1110101101 1100000011 0010110100
0010001011 1001011111 0101110000 1011001110 1111100100 0010101011 0001100101 1100111100 1110010010 0100010001
10 10
0011100111 0001110101 1000110000 1011001010 1111110100 0100000011 0110001111 1100111010 0100001100 1011011001
0111100000 1000100110 1000110101 1111010110 0000001011 1011011100 0111101111 0101100011 1100011000 0010011001
1 5
11110
00011
10 10
0110000111 1001101000 0000010001 1001010111 1010000110 1100100010 0101011011 1110111000 0011101101 0111111100
1110010110 1001111001 1110101001 0010011010 1101000111 0001000110 1011100011 0000111101 0100101100 0111010000
10 10
1111100111 1110010000 0000001110 0000100000 0110001001 0010011011 0101111110 1101011101 1011110011 1001100100
0100110111 0110001101 1111100011 1001100100 1011110001 1100010100 1001001010 0111111010 0000001110 0010011001
2 3
010 000
101 111
9 10
0101000001 1011101011 0010000001 1011011001 1011011011 0010111111 0101000010 1100000110 1001111100
0010111011 0010001011 1100100001 1100100010 0101100110 0000011100 0010111001 1011011111 1011100001
1 2
00
11
9 9
101111110 111010011 010110110 001001000 101101111 100011110 111101111 100100000 001000001
110111011 101100101 010101010 000100001 111011100 101111100 011110001 110001110 001110010
10 10
1001001101 1111011010 1110110100 0010101010 0001101101 1000000011 0101010110 1010110010 0101111101 0110000001
0000010101 0111101001 0111000010 1000001101 1011110010 1100001011 0100111110 1101100101 0011010010 1010111100
7 7
0011110 1011011 0111100 1101011 1111011 0110010 1101101
1011101 1001101 0111000 1111101 1001011 0011010 0010100
10 10
0011110011 1010000111 1100011100 1111111110 1101111111 0010100000 0000010000 0110100001 0001001101 1101001010
1111100010 1010011011 0110010110 1001111001 1000101111 0111000101 0101110101 0100101000 1000011010 0011000100
10 10
0111001111 1010100111 0000110010 0101101101 1000111101 1010011001 1010001100 0101010000 1111010010 0101100010
1011101001 1011010111 1011111100 0100011101 0100100000 0100010010 0110111111 0001000010 1001001101 1110100010
5 8
10001100 10010010 00110101 00100100 01001100
11010011 01111011 11001101 01101010 00010011
7 8
10100010 10110000 00101000 10000101 00000001 00111110 11001110
11011101 01000001 11001111 11111010 01010111 10110001 01111110
10 8
01000001 01100000 00000101 00111011 10001100 10001011 00000111 01101100 11011001 01110001
10010111 10001011 01011101 10110111 11011010 11110111 10110000 00110001 01001000 00001001
10 10
1110110000 1110101001 1001000011 0000111100 0101010111 0001101000 1110000101 0001101010 0011010111 1110011110
0100011101 0100000100 1001111010 1011000101 0011101110 0100110011 0100101000 1010010001 1111111010 1011000111
10 10
0010011001 1001000110 1100010000 0001101011 0111111100 0001100111 1111100000 0010100010 1110011111 1100011101
1011111110 1011110010 0100001010 0110001000 1000001100 0011010011 0101110101 1101101001 1000110111 0110000101
2 8
01011010 00011000
01011010 00011000
1 3
111
011
8 9
011000110 001001101 110011001 101000001 110001100 111011100 001000000 000110011
001000001 001001100 110011000 000110010 111011101 011000111 110001101 101000000
4 10
0010101001 1110000101 1001111001 1110111010
0100000110 0011111010 1111010110 0011000101
4 6
111110 111011 011000 010110
010111 010010 111111 110001
10 10
0011001011 1001110100 1110110000 0100001111 0010011110 0101010111 1100111001 0011100000 1011000000 1100101111
0101111010 0100000100 0011001101 1010100011 1101011010 1111101110 1010110101 0010010101 0101010001 1000101010
2 8
00110001 11000000
00110111 11000110
4 10
0000100011 1011100101 0000010011 1011010101
0100000011 1111000101 0100110011 1111110101
9 6
010011 010100 100010 100111 011001 001100 010111 110110 001110
001011 001100 010011 000110 111000 101001 010001 111101 001000
1 9
101010110
100010110
10 10
0100010111 1011101001 0000010010 0100101101 1011100010 1111111101 0100011100 1010000011 0111011110 1001100000
0011010101 1111100010 1100010001 1100100000 0010111111 1000101110 0011011110 0001011100 0111000001 1100101011
10 10
1010110010 0110101101 0011101110 0101010001 1000010010 1101100110 1000010000 1111011101 0010001001 0101101111
1111001000 1100110100 0001110111 1011101100 1100001010 0100000011 0011010111 0110111000 1010001011 0001110101
stdout
Case #1: 1
Case #2: NOT POSSIBLE
Case #3: NOT POSSIBLE
Case #4: NOT POSSIBLE
Case #5: NOT POSSIBLE
Case #6: NOT POSSIBLE
Case #7: NOT POSSIBLE
Case #8: NOT POSSIBLE
Case #9: 9
Case #10: NOT POSSIBLE
Case #11: NOT POSSIBLE
Case #12: NOT POSSIBLE
Case #13: 2
Case #14: NOT POSSIBLE
Case #15: NOT POSSIBLE
Case #16: NOT POSSIBLE
Case #17: NOT POSSIBLE
Case #18: NOT POSSIBLE
Case #19: NOT POSSIBLE
Case #20: NOT POSSIBLE
Case #21: NOT POSSIBLE
Case #22: 4
Case #23: NOT POSSIBLE
Case #24: NOT POSSIBLE
Case #25: NOT POSSIBLE
Case #26: NOT POSSIBLE
Case #27: NOT POSSIBLE
Case #28: NOT POSSIBLE
Case #29: 5
Case #30: NOT POSSIBLE
Case #31: NOT POSSIBLE
Case #32: NOT POSSIBLE
Case #33: NOT POSSIBLE
Case #34: NOT POSSIBLE
Case #35: NOT POSSIBLE
Case #36: 3
Case #37: NOT POSSIBLE
Case #38: 3
Case #39: NOT POSSIBLE
Case #40: NOT POSSIBLE
Case #41: NOT POSSIBLE
Case #42: NOT POSSIBLE
Case #43: 4
Case #44: NOT POSSIBLE
Case #45: NOT POSSIBLE
Case #46: NOT POSSIBLE
Case #47: NOT POSSIBLE
Case #48: NOT POSSIBLE
Case #49: NOT POSSIBLE
Case #50: NOT POSSIBLE
Case #51: NOT POSSIBLE
Case #52: NOT POSSIBLE
Case #53: 2
Case #54: NOT POSSIBLE
Case #55: NOT POSSIBLE
Case #56: NOT POSSIBLE
Case #57: NOT POSSIBLE
Case #58: NOT POSSIBLE
Case #59: NOT POSSIBLE
Case #60: NOT POSSIBLE
Case #61: NOT POSSIBLE
Case #62: NOT POSSIBLE
Case #63: NOT POSSIBLE
Case #64: NOT POSSIBLE
Case #65: NOT POSSIBLE
Case #66: NOT POSSIBLE
Case #67: NOT POSSIBLE
Case #68: 5
Case #69: NOT POSSIBLE
Case #70: NOT POSSIBLE
Case #71: NOT POSSIBLE
Case #72: NOT POSSIBLE
Case #73: 4
Case #74: NOT POSSIBLE
Case #75: NOT POSSIBLE
Case #76: NOT POSSIBLE
Case #77: NOT POSSIBLE
Case #78: 2
Case #79: NOT POSSIBLE
Case #80: NOT POSSIBLE
Case #81: NOT POSSIBLE
Case #82: NOT POSSIBLE
Case #83: NOT POSSIBLE
Case #84: NOT POSSIBLE
Case #85: NOT POSSIBLE
Case #86: NOT POSSIBLE
Case #87: NOT POSSIBLE
Case #88: NOT POSSIBLE
Case #89: NOT POSSIBLE
Case #90: 1
Case #91: NOT POSSIBLE
Case #92: NOT POSSIBLE
Case #93: NOT POSSIBLE
Case #94: NOT POSSIBLE
Case #95: NOT POSSIBLE
Case #96: NOT POSSIBLE
Case #97: NOT POSSIBLE
Case #98: 1
Case #99: NOT POSSIBLE
Case #100: NOT POSSIBLE