Solução Competição de Chocolate

Solução por Lucca Siaudzionis

Imagine que é sua vez de jogar agora, onde a pilha está com X chocolates, e você pode tirar qualquer quantidade de pedras de 1 a X-1. Vamos chamar de count[X] o número de jogadas ótimas que se podem fazer a partir de X (i.e. o número de jogadas possíveis que você possa fazer tal que você obrigatoriamente vai vencer se continuar jogando de maneira inteligente). Note que, se count[X] for maior que 1, você sempre vai poder vencer o jogo a partir daquela posição, pois, independente do valor que é proibido de ser retirado, você ainda tem outro valor disponível que lhe garante a vitória.

Note então que se count[X] \ = \ 0, quem receber uma pilha com X chocolates irá obrigatoriamente perder. Podemos então acrescentar 1count[X+1]count[X+2], ..., count[X+M-1] e count[X+M], pois quem começa com uma pilha com esses valores pode mandar para o adversário uma pilha com X chocolates.

Há, também, o caso que count[X] \ = 1, nesse caso, só há uma maneira de ganhar começando com uma pilha com X chocolates. Iremos então definir um outro valor forbid[X] que será definido para todo X, mas que só terá utilidade para este caso. Neste caso, forbid[X] será o valor que se tem que retirar, tendo uma pilha com X chocolates, para garantir a vitória. Com isso, caso uma pessoa receba uma pilha com X \ + \ forbid[X] chocolates, ela consegue ganhar se decidir retirar forbid[X] chocolates da pilha, ou seja, acrescentamos 1 a count[X \ + \ forbid[X]].

Calculando count[i] para todo i em que 1 \leq i \leq N, teremos que Paula irá ganhar se, e somente se, count[N] \geq 1 (pois Paula pode retirar qualquer valor menor que N da pilha).

O código então fica:


//
// 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;
}

view raw

chocolate.cpp

hosted with ❤ by GitHub