← 返回题目列表

AtCoder · codefestival_2015_final_c

C. 寿司塔

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

問題文

寿司是将「shihari」上放置「配料」的食物。

苹果先生 N 试图通过堆叠个寿司来制作寿司塔。N 个寿司意味着有N 个饭团 N 个配料,总共有 2N 个部分,但我们想按照某个顺序堆叠这些部分。

个寿司 1 种堆叠方法如下 3 种方式。

  • 直接堆叠:按饭团、配料的顺序堆叠。
  • 颠倒堆叠:按配料、饭团的顺序堆叠。
  • 拆开堆叠:将寿司拆开,分开饭团和配料,分别堆叠。

例如,3 个寿司如果想从下往上依次堆“配料、配料、配料、配料”,可以像下面这样堆。

  1. 个寿司 1 分段堆叠配料。饭团部分留着稍后堆叠。
  2. 将寿司原样堆放。
  3. 将寿司翻面后堆放。
  4. 堆放事先准备好的米饭。

拆开寿司很麻烦,因此小苹果希望尽量减少拆开的寿司数量。请找出为制作寿司塔而拆开的寿司的最小数量。


入力

输入是按以下格式从标准输入给出的。

N
S
  • 1 行表示寿司的数量的整数。 N (1 ≦ N ≦ 256) 。
  • 2 行表示堆放部件顺序的长度。 2N 的字符串 S 。S 是 N 个 0 和 我讨厌 N 个 1 组成的字符串,S 的 i (1≦i≦2N) 个字符是 0 当为 时表示从下往上堆放第 i 个米饭,1 当为 时表示从下往上堆放第 i 个配料。

出力

为制作目标寿司塔而拆开的寿司的最小数量 1 行输出。在输出末尾插入换行符。


入力例1

3
101100

出力例1

1

就像问题文中的例子一样。下图表示了堆放方式的例子,白色的圆表示寿司饭团,红色的矩形表示鱼料。

figure1

入力例2

5
0000111011

出力例2

3