分数: 450 点
问题陈述
对于二进制字符串 B = B_1 B_2 \dots B_{3^n} 长度 3^n (n \geq 1),我们定义一个操作来获取二进制字符串 C = C_1 C_2 \dots C_{3^{n-1}} 长度 3^{n-1} 如下:
- 对以下元素进行分区 B 分成几组 3 并从每组中获取多数值。也就是说,对于 i=1,2,\dots,3^{n-1},让 C_i 是其中出现最频繁的值 B_{3i-2}, B_{3i-1},和 B_{3i}.
给你一个二进制字符串 A = A_1 A_2 \dots A_{3^N} 长度 3^N。让 A' = A'_1 是长度-1 应用上述操作得到的字符串 N 次 A.
确定元素的最小数量 A 必须更改(从 0 to 1 或来自 1 to 0)以更改值 A'_1.
约束
- N 是一个整数 1 \leq N \leq 13.
- A 是一个长度为 3^N 组成 0 和 1.
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \dots A_{3^N}
输出
打印答案。
示例输入 1
2 010011101
示例输出 1
1
例如, A=010011101,应用两次操作后,我们得到:
- 第一次操作:大多数 010 is 0,属于 011 is 1,以及 101 is 1,导致 011.
- 第二次操作:大多数 011 is 1,产生 1.
更改最终值 1 to 0,一种方法是更改第 5 个字符 A 来自 1 to 0,产生 A=010001101。更改后,操作结果为:
- 第一次操作:大多数 010 is 0,属于 001 is 0,以及 101 is 1,导致 001.
- 第二次操作:大多数 001 is 0,产生 0.
因此,所需的最少更改次数是 1.
示例输入 2
1 000
示例输出 2
2