#P2039. [AHOI2009] 跳棋
[AHOI2009] 跳棋
题目描述
在一个 行 列( 是奇数)的棋盘上,有 个格子是红色的。这种情况下,你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子,在开始移动之间,你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是:每次只可以选择一个棋子,跳过与之相邻的棋子走到后面的空格上,被它跳过的棋子被吃掉,即从棋盘上移走,如相邻棋子的另一侧有棋子,则不能跳。
请回答以下两个问题:
- 移动开始前至少要放多少棋子才能完成任务。
- 如果要使开始前放的棋子数要求尽量少,那么在移动过程中最少需要放多少个棋子才能完成任务。
关于规则的补充说明:
- 只能往空位上放棋子,不管是移动开始前还是移动过程中。
- 移动前棋盘最左端的那个原始棋子绝对不能被吃掉。
输入格式
第一行一个正奇数 。
第二行有 个整数,如果第 个整数是 ,说明第 个格子是红棋,否则为白棋。
数字间用空格分开。
输出格式
两行,每行一个整数分别代表第一问和第二问的结果。
5
0 0 0 1 0
1
1
提示
在游戏开始前,可以在第二个格子上放上一个棋子,游戏开始后可用最左边的棋子吃掉它,从而移动到第三格。然后由于第四格是个红色的格子,在游戏中可以在那放一个棋子,然后用已经移动第三格的棋子把它吃掉,从而达到终点。
的数据中,,输出中的数字不超过 。
的数据中,。
Source: [Ahoi2009] checker