在 年,第八届初中生信息学奥林匹克决赛中出现了如下题目:
跳房子
Jasiu 喜欢和朋友们一起玩跳房子。他们一起决定对游戏规则稍作改进。一开始,在人行道上画出 个正方形格子,依次排列。格子从左侧开始从 起编号。某些格子上放有单个小石子。每位玩家选择一个起始格子,以及一个大于 的整数 。然后,从所选格子出发,每次跳 个格子,直到跳过第 号格子为止。玩家的得分等于其跳跃过程中落脚的有石子的格子数量。现在轮到 Jasiu 了,他非常想得到尽可能高的分数。已知石子的位置,请计算他能获得的最高分数。
输入格式
标准输入的第一行是一个整数 (),表示格子的数量。第二行是一个长度为 、由字符 . 和/或 # 组成的字符串。若第 个字符为 #,则第 个格子上有一颗石子,否则该格子为空。
输出格式
标准输出的唯一一行应输出一个整数,表示 Jasiu 能获得的最高分数。
样例
年的初中生如今已是参加 PA 的专业选手,可以期待他们现在对难度显著更高的题目感兴趣。在本版本中,石子的布局并非一开始就固定不变——我们从一个有 个格子的空棋盘开始,孩子们不断地添加和移除石子,每次操作后 Jasiu 都需要判断他能获得的最高分数。
注意: 网上也可以找到该题(原题)的题解,为方便起见我们也将其附于此处:https://www.youtube.com/live/jxYu1MGGjBc。但我们不保证其中的信息对解决我们这一版本的题目有任何帮助。