두 플레이어 A와 B가 게임을 하고 있다. 이 게임에는 1번부터 N번까지 번호가 매겨진 N개의 타일과, 가로로 N칸이 일렬로 놓인(처음에는 모두 비어 있는) 보드가 있다.

플레이어들은 번갈아 가며 턴을 진행하고, 플레이어 A가 먼저 시작한다. 한 턴에 플레이어는 아직 사용하지 않은 타일 하나와 비어 있는 칸 하나를 골라 그 칸에 타일을 놓는다. 게임이 끝났을 때, (누가 놓았는지와 무관하게) 번호가 연속인 두 타일이 서로 인접한 칸에 놓여 있으면 플레이어 A가 승리한다. 그렇지 않으면 플레이어 B가 승리한다. 예를 들어 최종 보드가 1 2 3 4이거나 4 1 3 2이면 플레이어 A의 승리이고, 최종 보드가 3 1 4 2이면 플레이어 B의 승리이다. (연속된 두 수가 등장하는 순서는 어느 쪽이어도 상관없다.)

당신은 방금 두 플레이어가 게임을 하는 것을 지켜봤지만, 그들의 전략을 이해할 수 없었다. 어쩌면 두 사람은 합리적으로 플레이하지 않았을지도 모른다! 당신은 그들의 수를 최적 전략과 비교해 보기로 했다.

승리 상태(winning state)란, 현재 차례인 플레이어가 최적으로 플레이할 경우 상대가 무엇을 하든 승리를 보장할 수 있는 게임 상태를 뜻한다. 실수(mistake)란, 승리 상태에서 어떤 수를 두어 다음 턴에 상대에게 승리 상태를 넘겨주는 수를 뜻한다. (마지막 턴에는 실수가 불가능함에 유의하라. 마지막 턴이 승리 상태에서 시작했다면, 그 플레이어가 둘 수 있는 유일한 수가 곧바로 승리로 이어질 수밖에 없기 때문이다.)

주어진 N번의 수를 바탕으로, 각 플레이어가 저지른 실수의 개수를 세어라.

#10382 upload 1 done 1 how_to_reg 1

Adjacent and Consecutive timer 40s memory 1024MB

#10382

Adjacent and Consecutive 40s 1024MB