#P2539. [AHOI2005] 矿藏编码

[AHOI2005] 矿藏编码

题目描述

探险机器人在 Samuel 星球发现了一片广阔的矿藏区。在这个矿藏区中,有高耸的山峰,也有平坦的平地。为了方便考察,整个矿藏区被划分 个格子区域。

例如下图,就是一个 K=2K=24×44 \times 4 的矿藏区:

其中黑色表示山峰,白色表示平地。

探险空间站已经将这片矿藏区的详细信息扫描并记录下来。由于矿藏区的面积实在太大,所以科学家们采用了一种特殊的编码方式记录。

  • 如果这片矿藏区全部是平地,则编码为 0
  • 如果这片矿藏区全部是山峰,则编码为 1
  • 否则,将矿藏区均匀划分成 44 份,如下 所示:

依次对每份进行编码,得 S1,S2,S3,S4S_1,S_2,S_3,S_4。该矿藏区的编码 SS2S1S2S3S42S_1S_2S_3S_4。 例如上图中,矿藏区的编码为:2021010210001

小联希望你能根据给定的编码统计出这片矿藏区一共有多少格子区域是平地。

输入格式

第一行有一个整数K,表示有矿藏区的规模为 KK1<K<501 < K < 50)。

第二行有一串编码,由 01 组成,长度不超过 200200,表示该矿藏区的编码。

输出格式

单行输出一个整数,表示矿藏区中一共有多少格子是平地。

2
2021010210001
9