← 返回题目列表

AtCoder · abc391_e

H. 等级多数投票

中文机器翻译题面 查看原题

分数: 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