fork download
copy 
  1. import static java.lang.Double.parseDouble;
  2. import static java.lang.Integer.parseInt;
  3. import static java.lang.Long.parseLong;
  4. import static java.lang.Math.min;
  5. import static java.lang.System.exit;
  6.  
  7. import java.io.BufferedReader;
  8. import java.io.IOException;
  9. import java.io.InputStreamReader;
  10. import java.io.OutputStreamWriter;
  11. import java.io.PrintWriter;
  12. import java.util.Arrays;
  13. import java.util.StringTokenizer;
  14.  
  15. class Ideone{
  16.  
  17. 	static BufferedReader in;
  18. 	static PrintWriter out;
  19. 	static StringTokenizer tok;
  20. 	static int test;
  21.  
  22. 	static void solve() throws Exception {
  23. 		int n = nextInt();
  24. 		boolean m[][] = new boolean[2 * n][2 * n];
  25. 		for (int i = 0; i < 2 * n; i++) {
  26. 			String l = next();
  27. 			for (int j = 0; j < 2 * n; j++) {
  28. 				m[i][j] = l.charAt(j) == '1';
  29. 			}
  30. 		}
  31. 		boolean h[] = m[0];
  32. 		int cnt = 0;
  33. 		for (int i = 0; i < 2 * n; i++) {
  34. 			if (h[i]) {
  35. 				++cnt;
  36. 			}
  37. 		}
  38. 		if (cnt != n) {
  39. 			printCase();
  40. 			out.println("IMPOSSIBLE");
  41. 			return;
  42. 		}
  43. 		boolean ih[] = new boolean[2 * n];
  44. 		for (int i = 0; i < 2 * n; i++) {
  45. 			ih[i] = !h[i];
  46. 		}
  47. 		boolean v[] = new boolean[2 * n];
  48. 		for (int i = 0; i < 2 * n; i++) {
  49. 			if (Arrays.equals(h, m[i])) {
  50. 				v[i] = false;
  51. 			} else if (Arrays.equals(ih, m[i])) {
  52. 				v[i] = true;
  53. 			} else {
  54. 				printCase();
  55. 				out.println("IMPOSSIBLE");
  56. 				return;
  57. 			}
  58. 		}
  59. 		cnt = 0;
  60. 		for (int i = 0; i < 2 * n; i++) {
  61. 			if (v[i]) {
  62. 				++cnt;
  63. 			}
  64. 		}
  65. 		if (cnt != n) {
  66. 			printCase();
  67. 			out.println("IMPOSSIBLE");
  68. 			return;
  69. 		}
  70. 		int cnt1 = 0, cnt2 = 0;
  71. 		for (int i = 0; i < 2 * n; i++) {
  72. 			if (h[i] != (i % 2 == 0)) {
  73. 				++cnt1;
  74. 			}
  75. 			if (v[i] != (i % 2 == 0)) {
  76. 				++cnt2;
  77. 			}
  78. 		}
  79. 		printCase();
  80. 		out.println((min(cnt1, 2 * n - cnt1) + min(cnt2, 2 * n - cnt2)) / 2);
  81. 	}
  82.  
  83. 	static void printCase() {
  84. 		out.print("Case #" + test + ": ");
  85. 	}
  86.  
  87. 	static void printlnCase() {
  88. 		out.println("Case #" + test + ":");
  89. 	}
  90.  
  91. 	static int nextInt() throws IOException {
  92. 		return parseInt(next());
  93. 	}
  94.  
  95. 	static long nextLong() throws IOException {
  96. 		return parseLong(next());
  97. 	}
  98.  
  99. 	static double nextDouble() throws IOException {
  100. 		return parseDouble(next());
  101. 	}
  102.  
  103. 	static String next() throws IOException {
  104. 		while (tok == null || !tok.hasMoreTokens()) {
  105. 			tok = new StringTokenizer(in.readLine());
  106. 		}
  107. 		return tok.nextToken();
  108. 	}
  109.  
  110. 	public static void main(String[] args) {
  111. 		try {
  112. 			in = new BufferedReader(new InputStreamReader(System.in));
  113. 			out = new PrintWriter(new OutputStreamWriter(System.out));
  114. 			int tests = nextInt();
  115. 			for (test = 1; test <= tests; test++) {
  116. 				solve();
  117. 			}
  118. 			in.close();
  119. 			out.close();
  120. 		} catch (Throwable e) {
  121. 			e.printStackTrace();
  122. 			exit(1);
  123. 		}
  124. 	}
  125. }
Success #stdin #stdout 0.13s 57944KB
comments (?)
stdin
copy 
100
8
1001110101000101
0110001010111010
1001110101000101
1001110101000101
0110001010111010
1001110101000101
0110001010111010
1001110101000101
0110001010111010
1001110101000101
0110001010111010
1001110101000101
0110001010111010
0110001010111010
0110001010111010
1001110101000101
3
001101
110110
001101
001111
110010
010010
2
1010
0101
1010
0101
4
11000101
11000101
00111010
00111010
11000101
00111010
00111010
11000101
5
0011100011
1100011100
1100011110
1100001110
1100011100
1100011100
0011100011
0011100011
0011100011
0011100011
1
10
10
2
0101
1010
1010
0101
2
1111
0111
1001
0001
3
010110
011100
110001
001011
100110
101001
3
100111
011010
100011
011010
011010
100101
8
1100001100111100
1000011100111100
1011010011000011
1100001100011110
0011110011000011
1100001100111100
0100101100111100
0011101011000011
1000010101111100
0011110011000011
1100001100111100
1010001100111100
0101110011000011
0111100011000011
0011110011100001
0111110010000011
1
10
01
2
0011
0011
1100
1100
3
010011
110100
101001
010110
101001
001110
3
010110
100110
011000
100011
010100
100011
3
100111
011001
110110
011011
000100
010001
2
1110
1110
0001
1110
1
01
10
4
01001000
01001101
01001101
10110011
01001001
10110010
10110010
00110000
10
01010100010100111101
10101011101011000010
10101011101011000010
10101011101011000010
01010100010100111101
01010100010100111101
10101011101011000010
01010100010100111101
01010100010100111101
01010100010100111101
01010100010100111101
01010100010100111101
10101011101011000010
01010100010100111101
10101011101011000010
01010100010100111101
10101011101011000010
10101011101011000010
10101011101011000010
10101011101011000010
4
10111100
01001011
01001111
10111100
10100100
00001011
01001011
10110101
4
11010100
00101011
00101011
11010100
11010100
11010100
00101011
00101011
2
1100
0011
1010
0101
1
01
00
1
10
01
1
01
10
3
011100
100011
100011
011100
100011
011100
2
1010
0101
1010
0101
1
11
10
4
11110001
00101110
11010001
10101110
11010001
00101110
11010001
00001110
7
10001011001011
10001011001011
01100100110100
10001011001011
10011011001011
01110100110100
01110100110100
01010100110100
10001011001011
01110100110100
01110100110100
01110100110100
10001011001011
10001011001011
3
011100
000111
010011
101001
100110
111000
2
1100
0111
0010
1110
2
1101
0101
0011
0011
4
01011010
01110010
10100101
10001110
00111001
10100101
11000101
01011010
2
0101
1001
1010
0110
2
0010
0111
0100
0100
1
01
10
2
0011
0110
0011
1110
1
01
10
6
011110010010
011110010010
100001101101
100001101101
011110010010
100001101101
100001101101
011110010010
100001101101
100001101101
011110010010
011110010010
4
01011001
01010011
10101100
10101100
01010011
10100110
11010001
00101110
1
00
11
1
01
10
4
11100100
11000100
00011011
00011010
11100100
01001011
11100100
00011011
4
10010011
10010011
01101100
01101100
01101100
01101100
10010011
10010011
3
001101
110010
001101
110010
001101
110010
1
01
10
1
10
01
2
0101
1010
1010
0101
2
0110
1001
1010
0101
5
1010101001
1000011110
1010101001
1010101001
0101010110
0101010110
0101010110
1010001011
0111100001
0101110100
5
0110000110
0110011110
1001110001
1101110001
0010001110
1001110001
0110001110
1001110001
0110000110
1000110001
7
01110101010001
10001010101110
01110101010001
10001010101110
01110101010001
10001010101110
01110101010001
01110101010001
01110101010001
10001010101110
10001010101110
10001010101110
01110101010001
10001010101110
3
100011
001110
100011
011100
011001
110100
5
0101110110
1010101001
1010101001
1010101001
1101010110
1101010110
0101010110
0101010110
1010101001
1010101001
9
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
100101010100010111
011010101011101000
1
01
10
4
10100011
10010011
01101100
00010011
10010011
00101100
01101100
11101110
9
101010101011001010
010101010100110101
010101010100110101
101010101011001010
010101010100110101
101010101011001010
010101010100110101
101010101011001010
010101010100110101
101010101011001010
010101010100110101
101010101011001010
010101010100110101
101010101011001010
010101010100110101
101010101011001010
010101010100110101
101010101011001010
1
01
10
1
10
01
3
110001
001110
110001
001110
110001
001110
2
0011
1100
1001
0110
4
10000111
01000111
01001101
11010010
10111000
00100111
01111000
10111000
3
111100
000011
100011
111100
100111
000100
10
01100001101010101011
10011110010101010100
01100001101010101011
10011110010101010100
01100001101010101011
10011110010101010100
01100001101010101011
10011110010101010100
01100001101010101011
10011110010101010100
01100001101010101011
10011110010101010100
01100001101010101011
10011110010101010100
10011110010101010100
10011110010101010100
01100001101010101011
10011110010101010100
01100001101010101011
01100001101010101011
1
10
01
4
01001011
10110100
10111000
01001011
01001011
10110100
10110100
01000111
1
10
10
2
1001
0101
1010
0110
4
11010100
10110001
11010001
10100110
01001011
01011001
00101110
00101110
2
1110
1100
0010
0001
4
10101100
01010011
01010011
10101100
10101100
01010011
01010011
10101100
2
1001
0110
0110
1001
3
000111
011010
011010
101001
110100
100101
5
0010011101
0010011101
1101100010
0010011101
1101100010
0010011101
0010011101
1101100010
1101100010
1101100010
2
0110
0110
1001
1001
10
01000111000110111001
01010111000110111000
01010111000110111000
10101000111001000111
10101000111001000111
01010111100110110000
01010111000110111000
10101000111001000111
10101000111001000111
10111000011001001110
01010111000110111000
10101000111001000111
01010111000110111000
10101000111001000111
10101000111001000111
01010111000110111000
01010110100110111000
01010111000110111000
10101001011001000111
10101000111001000111
2
0101
0000
1010
0101
1
01
10
3
010101
100110
001011
110100
111000
001011
2
0101
0101
1010
1010
2
1001
0110
0100
1001
1
10
01
4
00010111
11101000
11101000
00010111
11101000
00010111
00010111
11101000
9
110011001001001011
110011001001001011
001100110110110100
001100110110110100
110011001001001011
110011001001001011
001100110110110100
001100110110110100
001100110110110100
001100110110110100
001100110110110100
110011001001001011
110011001001001011
110011001001001011
001100110110110100
110011001001001011
110011001001001011
001100110110110100
3
001110
001110
001110
110001
110001
110001
4
01110001
01110001
10001110
10101001
10001110
10100110
01011001
01010110
9
100010101010101110
011101010101010001
100010101010101110
011101010101010001
100010101010101110
011101010101010001
100010101010101110
011101010101010001
100010101010101110
011101010101010001
100010101010101110
100010101010101110
100010101010101110
011101010101010001
100010101010101110
011101010101010001
011101010101010001
011101010101010001
1
00
01
4
00010111
01000111
10111000
01010110
10101001
10101001
01010110
11101000
5
0010110110
1001101010
0110010101
0111010100
1001001011
1001101010
1101101000
0110010101
0110010101
1000101011
1
00
10
2
1010
0101
1010
0101
5
1111010000
0100110101
1111001000
0000110111
1111000001
1111001000
0000101111
1011001010
0000111110
0000110111
3
011010
100101
011010
100101
100101
011010
4
01000101
01100101
00001011
01100101
11011010
10011010
01000101
10011010
4
11000110
01100011
01101001
10110100
00111001
10010110
01001011
10011100
5
1001101010
1001101010
0110010101
0110010101
1001101010
0110010101
0110010101
1001101010
1001101010
0110010101
stdout
copy 
Case #1: 4
Case #2: IMPOSSIBLE
Case #3: 0
Case #4: 3
Case #5: IMPOSSIBLE
Case #6: IMPOSSIBLE
Case #7: 1
Case #8: IMPOSSIBLE
Case #9: IMPOSSIBLE
Case #10: IMPOSSIBLE
Case #11: IMPOSSIBLE
Case #12: 0
Case #13: 2
Case #14: IMPOSSIBLE
Case #15: IMPOSSIBLE
Case #16: IMPOSSIBLE
Case #17: IMPOSSIBLE
Case #18: 0
Case #19: IMPOSSIBLE
Case #20: 6
Case #21: IMPOSSIBLE
Case #22: 3
Case #23: IMPOSSIBLE
Case #24: IMPOSSIBLE
Case #25: 0
Case #26: 0
Case #27: 2
Case #28: 0
Case #29: IMPOSSIBLE
Case #30: IMPOSSIBLE
Case #31: IMPOSSIBLE
Case #32: IMPOSSIBLE
Case #33: IMPOSSIBLE
Case #34: IMPOSSIBLE
Case #35: IMPOSSIBLE
Case #36: IMPOSSIBLE
Case #37: IMPOSSIBLE
Case #38: 0
Case #39: IMPOSSIBLE
Case #40: 0
Case #41: 6
Case #42: IMPOSSIBLE
Case #43: IMPOSSIBLE
Case #44: 0
Case #45: IMPOSSIBLE
Case #46: 4
Case #47: 1
Case #48: 0
Case #49: 0
Case #50: 1
Case #51: IMPOSSIBLE
Case #52: IMPOSSIBLE
Case #53: IMPOSSIBLE
Case #54: 2
Case #55: IMPOSSIBLE
Case #56: IMPOSSIBLE
Case #57: 2
Case #58: 0
Case #59: IMPOSSIBLE
Case #60: 2
Case #61: 0
Case #62: 0
Case #63: 1
Case #64: IMPOSSIBLE
Case #65: IMPOSSIBLE
Case #66: IMPOSSIBLE
Case #67: 4
Case #68: 0
Case #69: IMPOSSIBLE
Case #70: IMPOSSIBLE
Case #71: IMPOSSIBLE
Case #72: IMPOSSIBLE
Case #73: IMPOSSIBLE
Case #74: 3
Case #75: 2
Case #76: IMPOSSIBLE
Case #77: 4
Case #78: 2
Case #79: IMPOSSIBLE
Case #80: IMPOSSIBLE
Case #81: 0
Case #82: IMPOSSIBLE
Case #83: 1
Case #84: IMPOSSIBLE
Case #85: 0
Case #86: 3
Case #87: 8
Case #88: 2
Case #89: IMPOSSIBLE
Case #90: 2
Case #91: IMPOSSIBLE
Case #92: IMPOSSIBLE
Case #93: IMPOSSIBLE
Case #94: IMPOSSIBLE
Case #95: 0
Case #96: IMPOSSIBLE
Case #97: 2
Case #98: IMPOSSIBLE
Case #99: IMPOSSIBLE
Case #100: 3
https://ideone.com/MG0cqD
language:
Java (12.0.1)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!