chocolate.cpp

//
//  competicao_de_chocolate.cpp
//  programas2
//
//  Created by Lucca Siaudzionis on 29/04/14.
//  Copyright (c) 2014 Luccasiau. All rights reserved.
//

#include <cstdio>
#define MAXN 1001010

int n, m;
int count[MAXN];
int forbid[MAXN];

int solve(){
    /*
     Forbid[i] é o número de chocolates que eu tenho que tirar em i para vencer o jogo
     se forbid[i] for proibido, a posição i perde uma maneira de ganhar
     
     Count[i] é o número de maneiras que eu tenho de ganhar o jogo a partir da posição i
     se count[i] >= 2, a posição é estritamente vencedora (eu tenho duas jogadas possíveis que me fazem ganhar e ao máximo uma foi proibida)
     se count[i] = 1, a posição é perdedora <=> foi-se retirado forbid[i] na jogada anterior => count[i + forbid[i]]++
     se count[i] = 0, a posição é estritamente perdedora
     
     Note que precisamos apenas que count[n] >= 1 para que Paula ganhe, pois é a primeira jogada a ser feita
     */
    
    for(int i = 0;i <= n;i++) count[i] = forbid[i] = 0;
    
    for(int i = 0;i <= n;i++){
        
        if(!count[i]){ //se a posição for perdedora (note que eu começo com i = 0)
            for(int j = 1;j <= m;j++){ //faço todas as posições seguintes aumentarem seu valor de Count
                count[i+j]++;
                forbid[i+j] = j; //colocando um valor de forbid nelas (nao fará diferença se count[i+j] >= 2)
            }
        }
        else if(count[i] == 1 && i + forbid[i] <= n){ //se eu só tenho uma maneira de ganhar a partir de i, eu posso transformá-la numa posição perdedora
            count[i + forbid[i]]++; //bloqueando forbid[i], a posição i passa a ser perdedora
            forbid[i+ forbid[i]] = forbid[i];
        }
        
    }
    
    return count[n]; //se se tem alguma maneira de ganhar a partir de N, Paula ganha
}

int main(){
    
    scanf("%d %d",&n,&m);
    printf("%s\n", solve() ? "Paula" : "Carlos");
    
    return 0;
}