반박 불가능한 결과 timer 20s memory 1024MB

이자벨라(Izabella)와 올가(Olga)가 번갈아 가며 턴을 진행하는 게임을 하고 있다. 이자벨라가 먼저 플레이한다. 게임은 모든 말이 한 줄로 놓인 상태에서 시작한다. 말의 색은 두 가지로, 남색(indigo)과 주황색(orange)이 있다. 이자벨라의 턴에는, 남은 말들 중 맨 왼쪽 또는 맨 오른쪽에 있는 남색 말 하나를 골라 제거해야 한다. 올가의 턴에는, 남은 말들 중 맨 왼쪽 또는 맨 오른쪽에 있는 주황색 말 하나를 골라 제거해야 한다. 어떤 시점에든 한 플레이어가 둘 수 있는 합법적인 수가 없다면(남은 말이 하나도 없는 경우를 포함), 그 플레이어가 패배하고, 상대 플레이어는 1점을 얻으며, 추가로 보드에 남아 있는 말의 개수만큼(1점씩) 더 얻는다.

남색 말은 대문자 I로, 주황색 말은 대문자 O로 나타내자. 예를 들어 시작 보드가 IOIOOOII라고 하자.

첫 턴에서 이자벨라는 맨 왼쪽 말과 맨 오른쪽 말 중 어느 쪽을 제거해도 되는데, 둘 다 남색이기 때문이다. 이자벨라가 맨 왼쪽 말을 제거했다고 하자. 그러면 보드는 OIOOOII가 된다. 그 다음 올가는 선택의 여지 없이 새로 맨 왼쪽이 된 말을 제거해야 한다. 맨 오른쪽 말은 주황색이 아니기 때문이다. 그러면 보드는 IOOOII가 된다. 다시 이자벨라의 차례가 되고, 이번에는 맨 오른쪽 말을 제거했다고 하자. 그러면 올가의 차례에 보드는 IOOOI가 된다. 이제 올가는 합법적인 수가 없으므로, 이자벨라가 승리한다. 이때 남아 있는 말이 5개이므로, 이자벨라의 점수는 총 1+5=6점이다.

각 플레이어는 승리하는 것을 목표로 최적으로 플레이하며, 이길 수 있다면 자신의 점수를 최대화하려고 한다. 승리를 보장할 수 없는 플레이어는, 상대의 점수를 최소화하도록 플레이한다.

시작 보드가 주어질 때, 누가 이기며 승자의 점수는 얼마인지 구하라.