algorithm - 编程算法 : finding the winner of a competition

Question

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

Chocolate Competition

Carlos and Paula just got a bag of chocolate balls. As they would eat everything too quickly, they made a competition:

• They will eat alternately, one after the other (Paula always starts).
• Each time, they can only eat from 1 to M balls, M decided by Paula's mother, so they don't choke.
• If one ate K balls in his/her turn, the next can't eat K balls.
• Whoever can't play according the rules above loses.

在下面的示例中，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

请注意，最后 Carlos 没能吃到 2 个球来获胜，因为 Paula 在她的最后一个回合中吃了 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

假设我们有一个 bool 函数 FirstPlayerWin (FPW)，它有两个参数:剩下的巧克力数 (c) 和最后一步 (l)，即上一轮拿走的巧克力数，第一轮为 0移动。当且仅当第一个在这种情况下玩的玩家保证获胜时，例程返回 true。

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

否则，要计算 FPW(c, l)，如果对于任何 x <= M, x <= c, x != l，FPW(c - x, x) 为假，则 FPW(c, l) 为真.否则为假。这就是动态规划开始的地方，因为现在 FPW 的计算被简化为计算更小的 c 值的 FPW。

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

这样做的原因是，如果 FPW(c, 0) 为真(如果在巧克力计数 c 有任何移动可用，则先手获胜)但 FPW(c, x) 为假，因为 x > 0，FPW(c, y) for and y != x 必须为真。这是因为如果拒绝移动 x 会使玩家输掉，即玩家只能通过玩 x 获胜，那么移动 x 在 y 被禁止时可用。因此，对于任何计数“c”，最多存储一个导致玩家在那里输掉的禁止移动就足够了。所以你可以重构动态规划问题，这样你有两个数组而不是存储完整的二维数组 FPW(c, x)，一个存储值 FPW(c, 0)，另一个存储导致的单个禁止移动第一个输掉而不是赢的玩家，如果有的话。

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