小编Shi*_*ata的帖子

我将参加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