小红和小紫玩纸牌游戏,一共有 张纸牌,每张纸牌上有一个数字 或 。 小红和小紫轮流从牌堆中拿出一张牌,小红先手。游戏持续到牌堆中只剩下 张牌为止。最后剩下的 张牌按照从左到右的顺序组成一个二进制数。 小红的目标是使这个二进制数尽可能大,小紫的目标是使这个二进制数尽可能小。假设双方都采取最优策略,最后剩下的 张牌组成的二进制数是多少?
输入描述:
第一行输入两个整数 和 ,分别表示初始纸牌数量和最后剩余的纸牌数量。第二行输入一个长度为 的字符串,仅包含字符 '0' 和 '1',表示每张纸牌上的数字。


输出描述:
输出一个字符串,长度为 ,表示最后剩下的 张牌组成的二进制数。
示例1

输入

5 3
10110

输出

110

说明

初始状态下有 5 张牌:[1,0,1,1,0],需要保留 3 张牌。

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

最后剩下的三张牌是 [1,1,0],从左到右组成二进制数 "110"。

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