编程算法:寻找竞赛的赢家

Question

我将参加奥比(巴西信息学奥林匹克运动会，英语)，我正在尝试几个练习，从过去的几年。但是我找不到这个练习的解决方案(我翻译了它，所以可能有一些错误)：

巧克力大赛

卡洛斯和宝拉刚买了一袋巧克力球。因为他们吃东西太快，所以他们参加了一场比赛：

• 会轮流吃(宝拉总是开始吃)。
• 每次只能吃从1到M的球，M是由保拉的母亲决定的，所以他们不会窒息。
• 如果一人轮流吃K球，下一个就不能吃K球。不能按上述规则玩的
• 输掉了。

F 211

在下面使用M=5和20个球的例子中，Carlos赢了：

Who plays        How many ate        Balls left

                                     20
Paula            5                   15
Carlos           4                   11
Paula            3                   8
Carlos           4                   4
Paula            2                   2
Carlos           1                   1

最后要注意的是，卡洛斯不能吃两个球才能赢，因为宝拉在最后一回合吃了2个球。但是保拉不能吃最后一球，因为卡洛斯在最后一回合吃了1球，所以保拉不能打，也输不了。

这两个人都很聪明，而且玩得很好。如果有一个回合序列，确保他/她的胜利独立于其他回合，他/她将播放这些序列。

任务：

你的任务是找出谁将赢得竞争，如果双方发挥最佳。

输入：

输入只包含一个测试组，应该从标准输入(通常是键盘)中读取。

输入有2个整数N (2≤N≤1000000)和M (2≤M≤1000)，即N为球数，M为每轮允许的数。

输出：

您的程序应该在标准输出中打印一行，其中包含获胜者的姓名。

示例：

Input:          Output:
5 3             Paula
20 5            Carlos
5 6             Paula

我一直在努力解决这个问题，但我不知道怎么解决。

在这里可以找到C中的一个解决方案：http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txt，但我无法理解算法。有人在另一个网站上发布了一个关于这个问题的问题，但没有人回答。

你能解释一下算法吗？

下面是程序的预期输出：http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip

Answer 1

假设我们有一个布尔函数FirstPlayerWin (FPW)，它接受两个参数:剩下的巧克力数(c)和最后一步(l)，也就是上一轮的巧克力数，第一步是0。例程返回真当且仅当在这种情况下第一名球员保证获胜。

基本情况是FPW(0，l) = false对于任何l != 1

否则，若对任意x <= M，x <= c，x != l，FPW(c - x，x)为false，则计算FPW(c，l)为真。否则就是假的。这就是动态规划开始的地方，因为现在FPW的计算简化为对c值较小的FPW的计算。

但是，存储用于此公式的条目将需要N*M表条目，其中您所指向的解决方案仅使用2N表条目。

这样做的原因是，如果FPW(c，0)是真的(如果巧克力计数c有任何移动，那么第一个玩家就会赢)，但是FPW(c，x)对于x> 0是假的，FPW(c，y) for和y != x必须是true。这是因为如果拒绝移动x会让玩家输掉，也就是说，玩家只会通过玩x赢，那么当y被禁止时，移动x是可用的。因此，这是足够存储任何计数'c‘在最多一个禁止的移动，导致球员输在那里。因此，您可以重构动态规划问题，这样，与其存储完整的二维数组FPW(c，x)，您有两个数组，一个存储值FPW(c，0)，另一个存储导致第一个玩家失败而不是获胜的单个禁止的移动。

如何获得引用的C程序的确切文本是留给读者的练习。

Answer 2

我认为这是动态规划中又一种伪装的练习。游戏的状态由两个量描述:剩下的球数和在前一个动作中吃掉的球数。当剩下的球数为<= M时，游戏要么获胜(如果剩余的数量不等于上一次移动中所吃的数)，要么输掉(如果是的话--你不能吃掉所有的球，而你的对手可以吃掉你剩下的球)。

如果你已经算出了所有数到H的球的赢/输情况，以及前一位球员吃掉的所有可能的球数，并把它写在一张桌子上，那么你就可以算出直到H+1的所有数目的球的答案。一个在前一个动作中吃了H+1球和k个球的球员会考虑所有的可能性--除了k的违法值外，吃I=1比M的球。留下一个H+1-i球的位置和i的前一个动作。他们可以使用这张表给出赢-输的情况，直到H球离开，尝试找到一个合法的k来给他们一个胜利。如果他们能找到这样的值，H+1/k位置就是胜利。如果不是，这是一个损失，所以他们可以扩展表来掩盖H+1球，等等。

我还没有完成所有未注释的示例代码，但看起来它可能会这样做--使用递归之类的动态编程来构建一个表。