/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
長さ 3^n \; (n \geq 1) の 01 列 B=B_1 B_2 \dots B_{3^n} に対して、長さ 3^{n-1} の 01 列 C=C_1 C_2 \dots C_{3^{n-1}} を得る操作を以下のように定めます。
- B の要素を 3 つずつまとめて多数決を取る。すなわち、i=1,2,\dots,3^{n-1} について、B_{3i-2},B_{3i-1},B_{3i} のうち最も多く現れる値を C_i とする。
長さ 3^N の 01 列 A = A_1 A_2 \dots A_{3^N} が与えられます。A に上の操作を N 回適用して得られる長さ 1 の列を A' = A'_1 とします。
A の要素のいくつかを 0 から 1 または 1 から 0 へ変えることを考えたとき、A の要素を最小で何個変えれば、A'_1 の値が変わるか求めてください。
制約
- N は 1 以上 13 以下の整数
- A は 0,1 からなる長さ 3^N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \dots A_{3^N}
出力
答えを出力せよ。
入力例 1
2 010011101
出力例 1
1
A=010011101 に操作を 2 回適用すると、以下のようになります。
- 1 回目： 010 の過半数は 0, 011 の過半数は 1, 101 の過半数は 1 なので、これらをつなげて 011 を得る。
- 2 回目： 011 の過半数は 1 なので、 1 を得る。
最終的な値を 1 から 0 にするためには、例えば A の 5 文字目を 1 から 0 にして A=010001101 にすればよいです。変更後、操作は以下のようになります。
- 1 回目： 010 の過半数は 0, 001 の過半数は 0, 101 の過半数は 1 なので、これらをつなげて 001 を得る。
- 2 回目： 001 の過半数は 0 なので、 0 を得る。
よって、 A の要素を 1 個変えるのが最小です。
入力例 2
1 000
出力例 2
2
Score : 450 points
Problem Statement
For a binary string B = B_1 B_2 \dots B_{3^n} of length 3^n (n \geq 1), we define an operation to obtain a binary string C = C_1 C_2 \dots C_{3^{n-1}} of length 3^{n-1} as follows:
- Partition the elements of B into groups of 3 and take the majority value from each group. That is, for i=1,2,\dots,3^{n-1}, let C_i be the value that appears most frequently among B_{3i-2}, B_{3i-1}, and B_{3i}.
You are given a binary string A = A_1 A_2 \dots A_{3^N} of length 3^N. Let A' = A'_1 be the length-1 string obtained by applying the above operation N times to A.
Determine the minimum number of elements of A that must be changed (from 0 to 1 or from 1 to 0) in order to change the value of A'_1.
Constraints
- N is an integer with 1 \leq N \leq 13.
- A is a string of length 3^N consisting of 0 and 1.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_{3^N}
Output
Print the answer.
Sample Input 1
2 010011101
Sample Output 1
1
For example, with A=010011101, after applying the operation twice, we obtain:
- First operation: The majority of 010 is 0, of 011 is 1, and of 101 is 1, resulting in 011.
- Second operation: The majority of 011 is 1, yielding 1.
To change the final value from 1 to 0, one way is to change the 5th character of A from 1 to 0, yielding A=010001101. After the change, the operations yield:
- First operation: The majority of 010 is 0, of 001 is 0, and of 101 is 1, resulting in 001.
- Second operation: The majority of 001 is 0, yielding 0.
Thus, the minimum number of changes required is 1.
Sample Input 2
1 000
Sample Output 2
2