title: Programming algorithm: finding the winner of a competition
body: <p>I will compete in the OBI (Brazilian Olympiad of Informatics, in English) and I am trying a few exercises from the last years. But I can't find a solution for this exercise (I translated it, so there may be a few errors):</p>
  
  <blockquote>
    <p>Chocolate Competition</p>
    
    <p>Carlos and Paula just got a bag of chocolate balls. As they would eat
    everything too     quickly, they made a competition:</p>
    
    <ul>
    <li>They will eat alternately, one after the other (Paula always starts).</li>
    <li>Each time, they can only eat from 1 to M balls, M decided by Paula's mother, so they don't choke.</li>
    <li>If one ate K balls in his/her turn, the next can't eat K balls.</li>
    <li>Whoever can't play according the rules above loses.</li>
    </ul>
  </blockquote>
  
  <p>In the example below with M = 5 and 20 balls, Carlos has won:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Note that in the end, Carlos couldn't eat 2 balls to win, because Paula ate 2 in her last turn. But Paula couldn't eat the last ball, because Carlos ate 1 in his last turn, so Paula can't play and loses.</p>
  
  <p>Both are very smart and play optimally. If there is a sequence of turns that ensures him/her the victory independent of the other's turns, he/she will play these sequences.</p>
  
  <p>Task:</p>
  
  <p>Your task is to find out who will win the competition if both play optimally.</p>
  
  <p>Input:</p>
  
  <p>The input contains only a single test group, which should be read from the standard input (usually the keyboard).</p>
  
  <p>The input has 2 integers N (2 ≤ N ≤ 1000000) and M (2 ≤ M ≤ 1000), being N the number of balls and M the number allowed per turn.</p>
  
  <p>Output:</p>
  
  <p>Your program should print, in the standard output, one line containing the name of the winner.</p>
  
  <p>Examples:</p>
  
  <pre><code>Input:          Output:
  5 3             Paula
  20 5            Carlos
  5 6             Paula
  </code></pre>
  
  <p>I've been trying to solve the problem, but I have no idea how.</p>
  
  <p>A solution in C can be found here: <a href="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/solucoes/chocolate.c.txt</a> But I can't understand the algorithm. Someone posted a question about this problem in another site, but nobody replied.</p>
  
  <p>Could you explain me the algorithm?</p>
  
  <p>Here are the expected outputs of the program: <a href="http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip">http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip</a></p>