第一行输入两个整数 和 ,分别表示初始纸牌数量和最后剩余的纸牌数量。第二行输入一个长度为 的字符串,仅包含字符 '0' 和 '1',表示每张纸牌上的数字。
输出一个字符串,长度为 ,表示最后剩下的 张牌组成的二进制数。
5 3 10110
110
初始状态下有 5 张牌:,需要保留 3 张牌。
游戏过程:
1. 小红先手,为了使最终数字尽可能大,她会拿走从左到右第一个 0
2. 小紫为了使最终数字尽可能小,她会拿走最后一个 1
最后剩下的三张牌是,从左到右组成二进制数 "110"。
可以证明,在双方都采取最优策略的情况下,这是最终可能得到的结果。