Leia o enunciado antes de continuarmos.
Como de costume, para resolver o problema usando DP temos de encontrar uma descrição recursiva da solução.
Seja bachet(N) igual a 1 se o próximo jogador ganha com N pedras em jogo, e seja igual a 2 no caso contrário (ie, o seu adversário ganha).
Seja moves[ ] o vector com as retiradas de pedras possível.
Uma posição é vencedora se houver uma jogada que torne a posição resultante numa posição perdedora (pois será a vez do adversário jogar), ou seja, para bachet[N] = 1, tem de existir pelo menos uma posição bachet(N - moves[i]) = 2, porque isso significa que com N-moves[i] pedras, a vitória será, não do próximo jogador mas do seu adversário (ie, o jogador actual, dado que os jogadores alternam a vez).
Temos assim a nossa relação de recorrência:
bachet(N) = 1 sse existe i : bachet[N - moves[i]] == 2
bachet(N) = 2 caso contrário
E não nos podemos esquecer da base da recursão: uma mesa com zero pedras é uma derrota do próximo jogador
bachet(0) = 2
Traduzindo esta relação para Java:
static final int UNKNOWN = 0;
static int bachet(int N) {
if (sols[N] == UNKNOWN) {
sols[N] = 2; // assume victory for 2nd player, unless:
for(int move=0; move<moves.length; move++)
if (N>=moves[move] && bachet(N-moves[move])==2)
sols[N] = 1;
}
return sols[N];
}
Este tipo de abordagem de começar no N final e ir descendo para valores mais pequenos chama-se uma abordagem top-down. Ela tem uma vantagem: só são calculadas as soluções necessários ao cálculo de bachet(N).
Por exemplo, se N=30, e moves = [7,10,15] obtemos este array de soluções
sols = [2, 2, 2, 2, 0, 2, 2, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1]
Todas as posições zero não foram calculadas porque não faziam parte do cálculo de bachet(30). Isto pode significar grandes poupanças de tempo!
A desvantagem é que a forma natural de resolver por top-down é usar recursão, e isso pode levantar problemas de StackOverflow para números muito grandes (como neste caso, dado que o N pode ser 1000000).
A alternativa é uma abordagem bottom-up cuja forma natural de resolver é usar iteração, e que neste caso nos garante uma solução. Uma solução bottom-up começa da solução com zero pedras e vai construíndo o vector de soluções passo a passo:
static int bachet(int N) {
for(int i=1; i<=N; i++) {
sols[i] = 2; // assume victory for 2nd player, unless:
for(int move=0; move<moves.length; move++)
if (i-moves[move] >= 0 && sols[i-moves[move]] == 2)
sols[i] = 1;
}
return sols[N];
}
Isto significa que o vector de soluções é totalmente calculado. No exemplo anterior teríamos:
sols = [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1]
O resto do programa para ler e imprimir os resultados:
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int N = sc.nextInt();
int nMoves = sc.nextInt();
moves = new int[nMoves];
for(int i=0; i<nMoves; i++)
moves[i] = sc.nextInt();
sols = new int[N+1];
sols[0] = 2;
System.out.printf("%s wins\n", bachet(N) == 1 ? "Stan" : "Ollie");
}
sc.close();
}