首页 > 试题广场 >

小红的纸牌游戏

[编程题]小红的纸牌游戏

热度指数：595 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小红和小紫玩纸牌游戏，一共有 $n$ 张纸牌，每张纸牌上有一个数字 $0$ 或 $1$ 。

小红和小紫轮流从牌堆中拿出一张牌，小红先手。游戏持续到牌堆中只剩下 $k$ 张牌为止。最后剩下的 $k$ 张牌按照从左到右的顺序组成一个二进制数。

小红的目标是使这个二进制数尽可能大，小紫的目标是使这个二进制数尽可能小。假设双方都采取最优策略，最后剩下的 $k$ 张牌组成的二进制数是多少？

输入描述:

第一行输入两个整数  和 ，分别表示初始纸牌数量和最后剩余的纸牌数量。
第二行输入一个长度为  的字符串，仅包含字符 '0' 和 '1'，表示每张纸牌上的数字。

输出描述:

输出一个字符串，长度为 ，表示最后剩下的  张牌组成的二进制数。

示例1

输入

5 3
10110

输出

说明

初始状态下有 5 张牌：，需要保留 3 张牌。

游戏过程：
1. 小红先手，为了使最终数字尽可能大，她会拿走从左到右第一个 0
2. 小紫为了使最终数字尽可能小，她会拿走最后一个 1

最后剩下的三张牌是 ，从左到右组成二进制数 "110"。

可以证明，在双方都采取最优策略的情况下，这是最终可能得到的结果。