Vamos jogar um jogo:

Existem n pilhas de moedas seguidas. i-ésima pilha consiste em moedas d_i. Dois jogadores: Jogador1, Jogador2 faz movimentos alternadamente. O jogador, por sua vez, só pode receber a primeira pilha, a última pilha ou os dois. O jogo termina quando não há mais moedas. Cada jogador quer ter tantas moedas quanto possível no final. Jogador1 começa.

Eu estava me perguntando sobre o algoritmo (soa como algoritmo guloso) para contar quantas moedas cada jogador tem no final do jogo quando ambos jogam otimamente.

Eu não tenho ideia de como abordar esses algoritmos. Basta adivinhar estratégia ou há alguma maneira de deduzir isso? Ou talvez seja um problema muito estranho implementar um algoritmo?

Exemplos (moedas em pilhas do primeiro ao n-ésimo):

1, 100, 1 - os jogadores têm 2 e 100 moedas respectivamente (infelizmente, o primeiro jogador só pode receber a primeira e a última pilha - o segundo jogador receberá sempre uma pilha com 100 moedas)

1, 1, 100, 1, 1, 5 - os jogadores têm 8 e 101 moedas, respectivamente (acho que é depois do jogo ideal - primeiro tire 5 e 1, depois segure 1 para evitar que o jogador 1 fique com 100 moedas). tomar menos de 6 moedas em sua primeira jogada, ele sempre terá menos de 8 moedas).

Espero ter especificado o problema. Você concorda que é interessante? :) Alguém pode ajudar?