我将参加OBI(巴西信息学奥林匹克,英语),我正在尝试过去几年的一些练习.但是我找不到这个练习的解决方案(我翻译了它,所以可能会有一些错误):
巧克力比赛
Carlos和Paula刚买了一袋巧克力球.因为他们会吃得太快,所以他们参加了比赛:
- 他们会一个接一个地交替吃饭(宝拉总是开始).
- 每次,他们只能吃1到M个球,M由Paula的母亲决定,所以他们不会窒息.
- 如果一个人在他/她的回合吃了K球,那么接下来就不能吃K球了.
- 谁不能按照上述规则进行比赛就输了.
在下面的例子中,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球,因为宝拉在最后一回合吃了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
假设我们有一个布尔函数 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) 为 false，则 FPW(c, l) 为 true。否则就是假的。这就是动态规划发挥作用的地方，因为现在 FPW 的计算被简化为计算较小 c 值的 FPW。
但是，存储此公式的条目将需要 N * M 表条目，而您指出的解决方案仅使用 2N 表条目。
这样做的原因是，如果 FPW(c, 0) 为真（如果巧克力计数 c 处有任何移动，则第一个玩家获胜），但当 x > 0 时 FPW(c, x) 为假，则 FPW(c, y) 为并且 y != x 必须为真。这是因为，如果拒绝移动 x 会使玩家输掉，即玩家仅通过玩 x 才能获胜，那么当 y 被禁止时，移动 x 才可用。因此，对于任何计数“c”，最多存储一个导致玩家失败的禁止动作就足够了。因此，您可以重构动态规划问题，这样您就可以拥有两个数组，而不是存储完整的二维数组 FPW(c, x)，一个存储值 FPW(c, 0)，另一个存储导致 FPW(c, 0) 的单个禁止移动第一个失败而不是获胜的玩家（如果有的话）。
如何获得引用的 C 程序的确切文本留给读者作为练习。