{"raw_statement":[{"iden":"statement","content":"Magnus decided to play a classic chess game. Though what he saw in his locker shocked him! His favourite chessboard got broken into 4 pieces, each of size _n_ by _n_, _n_ is **always odd**. And what's even worse, some squares were of wrong color. _j_\\-th square of the _i_\\-th row of _k_\\-th piece of the board has color _a__k_, _i_, _j_; 1 being black and 0 being white.\n\nNow Magnus wants to change color of some squares in such a way that he recolors minimum number of squares and obtained pieces form a valid chessboard. Every square has its color different to each of the neightbouring by side squares in a valid board. Its size should be 2_n_ by 2_n_. You are allowed to move pieces but **not allowed to rotate or flip them**."},{"iden":"input","content":"The first line contains **odd** integer _n_ (1 ≤ _n_ ≤ 100) — the size of all pieces of the board.\n\nThen 4 segments follow, each describes one piece of the board. Each consists of _n_ lines of _n_ characters; _j_\\-th one of _i_\\-th line is equal to _1_ if the square is black initially and _0_ otherwise. Segments are separated by an empty line."},{"iden":"output","content":"Print one number — minimum number of squares Magnus should recolor to be able to obtain a valid chessboard."},{"iden":"examples","content":"Input\n\n1\n0\n\n0\n\n1\n\n0\n\nOutput\n\n1\n\nInput\n\n3\n101\n010\n101\n\n101\n000\n101\n\n010\n101\n011\n\n010\n101\n010\n\nOutput\n\n2"}],"translated_statement":[{"iden":"statement","content":"Magnus 决定玩一局经典的国际象棋游戏。但他打开储物柜时震惊了！他最爱的棋盘被摔成了 #cf_span[4] 块，每块大小为 #cf_span[n] 乘 #cf_span[n]，且 #cf_span[n] 始终为奇数。更糟糕的是，有些格子的颜色错了。第 #cf_span[k] 块棋盘的第 #cf_span[i] 行第 #cf_span[j] 列的格子颜色为 #cf_span[ak, i, j]；其中 #cf_span[1] 表示黑色，#cf_span[0] 表示白色。\n\n现在 Magnus 希望通过改变一些格子的颜色，使得他重新着色的格子数量最少，并且这些块能拼成一个合法的棋盘。在一个合法的棋盘中，每个格子的颜色必须与所有相邻（共享边）的格子不同。最终棋盘的大小应为 #cf_span[2n] 乘 #cf_span[2n]。你可以移动这些块，但不允许旋转或翻转它们。\n\n第一行包含一个奇数整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 100)] —— 每块棋盘的大小。\n\n接下来是 #cf_span[4] 个段落，每个描述一块棋盘。每个段落包含 #cf_span[n] 行，每行有 #cf_span[n] 个字符；第 #cf_span[i] 行第 #cf_span[j] 个字符为 _1_ 表示该格子初始为黑色，为 _0_ 表示白色。段落之间用空行分隔。\n\n输出一个数字 —— Magnus 为获得一个合法棋盘所需重新着色的最少格子数。"},{"iden":"input","content":"第一行包含一个奇数整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 100)] —— 每块棋盘的大小。接下来是 #cf_span[4] 个段落，每个描述一块棋盘。每个段落包含 #cf_span[n] 行，每行有 #cf_span[n] 个字符；第 #cf_span[i] 行第 #cf_span[j] 个字符为 _1_ 表示该格子初始为黑色，为 _0_ 表示白色。段落之间用空行分隔。"},{"iden":"output","content":"输出一个数字 —— Magnus 为获得一个合法棋盘所需重新着色的最少格子数。"},{"iden":"examples","content":"输入10010输出1输入3101010101101000101010101011010101010输出2"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an odd integer, $ 1 \\leq n \\leq 100 $.  \nLet $ P_1, P_2, P_3, P_4 $ be four $ n \\times n $ binary matrices representing the four chessboard pieces, where $ P_k[i][j] \\in \\{0,1\\} $ denotes the color of the square at row $ i $, column $ j $ of piece $ k $ (1 = black, 0 = white).\n\n**Constraints**  \n- Each piece $ P_k $ has dimensions $ n \\times n $.  \n- The final board is a $ 2n \\times 2n $ chessboard formed by arranging the four pieces in a $ 2 \\times 2 $ grid (no rotation or flipping allowed).  \n- A valid chessboard requires that every two adjacent (by side) squares have opposite colors.  \n- Thus, the entire $ 2n \\times 2n $ board must follow a checkerboard pattern: for any position $ (r, c) $, the color must equal $ (r + c) \\mod 2 $ (or its inverse).\n\n**Objective**  \nDetermine the minimum number of square recolorings over all possible assignments of the four pieces to the four quadrants of the $ 2n \\times 2n $ board such that the resulting board is a valid chessboard.\n\nLet $ \\sigma \\in S_4 $ be a permutation assigning pieces $ P_1, P_2, P_3, P_4 $ to the four quadrants:  \n- Top-left: $ (r, c) \\in \\{0, \\dots, n-1\\} \\times \\{0, \\dots, n-1\\} $  \n- Top-right: $ (r, c) \\in \\{0, \\dots, n-1\\} \\times \\{n, \\dots, 2n-1\\} $  \n- Bottom-left: $ (r, c) \\in \\{n, \\dots, 2n-1\\} \\times \\{0, \\dots, n-1\\} $  \n- Bottom-right: $ (r, c) \\in \\{n, \\dots, 2n-1\\} \\times \\{n, \\dots, 2n-1\\} $\n\nFor each quadrant position, the target color at local position $ (i, j) $ (within the piece) is determined by the global position:  \n- Top-left: target = $ (i + j) \\mod 2 $  \n- Top-right: target = $ (i + j + n) \\mod 2 $  \n- Bottom-left: target = $ (i + j + n) \\mod 2 $  \n- Bottom-right: target = $ (i + j + 2n) \\mod 2 = (i + j) \\mod 2 $\n\nThus, for each piece assigned to a quadrant, the number of recolorings required is the Hamming distance between the piece and the target checkerboard pattern for that quadrant.\n\nLet $ C_k(\\sigma) $ be the cost (number of mismatches) of assigning piece $ P_k $ to quadrant $ \\sigma(k) $.\n\nThen the objective is:  \n$$\n\\min_{\\sigma \\in S_4} \\sum_{k=1}^{4} C_k(\\sigma)\n$$","simple_statement":null,"has_page_source":false}