8

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

巧克力大赛

卡洛斯和宝拉刚拿到一袋巧克力球。由于他们吃得太快，他们进行了比赛：

  • 他们会一个接一个地交替进食（宝拉总是开始）。
  • 每次只能吃1到M个丸子，M由Paula的妈妈决定，所以他们不会噎着。
  • 如果一个人轮到他/她吃 K 个球，那么下一个不能吃 K 个球。
  • 谁不能按上述规则比赛谁输。

在下面的示例中，M = 5 和 20 个球，卡洛斯赢了：

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 个球来获胜，因为宝拉在最后一回合吃了 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

4

2 回答 2

3

假设我们有一个布尔函数 FirstPlayerWin (FPW)，它接受两个参数：剩下的巧克力数量 (c) 和最后一步 (l)，即上一轮采取的巧克力数量，在第一步时为 0。当且仅当第一个在这种情况下比赛的玩家保证获胜时，该例程才会返回 true。

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

否则，要计算 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) 对于并且 y != x 必须为真。这是因为如果拒绝移动 x 会使玩家输掉，即玩家只能通过下 x 来获胜，那么当 y 被禁止时，移动 x 是可用的。因此，对于任何计数“c”，最多存储一个导致玩家输掉的禁止移动就足够了。因此，您可以重构动态规划问题，以便您拥有两个数组，而不是存储完整的二维数组 FPW(c, x)，一个存储值 FPW(c, 0)，另一个存储导致的单个禁止移动第一个输掉而不是赢的玩家，如果有的话。

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

于 2012-05-12T05:47:14.067 回答
0

我认为这是动态编程中又一个隐蔽的练习。游戏的状态由两个量来描述：剩余的球数和上一步吃掉的球数。当剩余的球数 <= M 时，游戏要么赢（如果剩余的数量不等于前一步吃掉的数量）或输（如果是 - 你不能吃掉所有的球，并且你的对手可以吃掉你留下的球）。

如果你已经计算出最多 H 的所有球数的输赢情况，以及前一个玩家吃掉的所有可能的球数并将其写在表格中，那么你可以计算出所有球数的答案最多 H+1。一个有 H+1 个球和 k 个球在前一步吃掉的玩家会考虑所有的可能性 - 吃 i 个球，因为 i = 1 到 M，除了 k 的非法值，留下一个有 H+1-i 个球和前一个球的位置i的移动。他们可以使用表格给出最多 H 个球的输赢情况，尝试找到一个合法的 k 让他们获胜。如果他们能找到这样的值，那么 H+1/k 的位置就是胜利。如果没有，那就是损失，所以他们可以扩大桌子以覆盖 H+1 个球，依此类推。

我还没有完成所有未注释的示例代码，但看起来它可能正在做这样的事情 - 使用像递归这样的动态编程来构建表。

于 2012-05-12T04:34:45.497 回答