Yet Another Stone Game

후공이 이기는 상태를 패배 상태라고 하자. $O$를 홀수인 돌 더미의 개수, $M$을 모든 돌 더미 크기의 최솟값이라고 하자.

가능한 $K$는 $N-2$, $N-1$, $N$뿐이다. 단, $N=3$, $K=1$인 경우는 따로 처리한다.

$K=1$인 경우

한 번 행동할 때마다 전체 돌의 수가 정확히 $1$ 감소한다. 따라서 게임의 전체 행동 횟수는 $\sum A_i$로 고정된다. 이 합이 짝수일 때만 패배 상태이다.

$K=N$인 경우

모든 돌 더미가 짝수인 상태가 정확히 패배 상태이다. 이 상태에서 한 번 행동하면 적어도 하나의 더미가 홀수가 된다. 반대로 홀수인 더미가 하나라도 있으면 홀수인 더미를 전부 골라 모든 더미를 짝수로 만들 수 있다.

$K=N-1$인 경우

모든 더미의 홀짝이 같은 상태가 정확히 패배 상태이다. 모든 더미가 짝수이거나 모든 더미가 홀수인 상태에서 $1$개 이상 $N-1$개 이하의 더미를 고르면 두 홀짝이 섞인다. 반대로 두 홀짝이 섞인 상태에서는 홀수인 더미를 전부 골라 모든 더미를 짝수로 만들 수 있다.

$K=N-2$인 경우

이 경우에는 $N\geq4$이다. 다음 두 종류가 정확히 패배 상태이다.

• 모든 더미가 짝수이다.
• 홀수인 더미가 $N-1$개이고, 유일한 짝수 더미의 크기가 전체의 최솟값이다.

첫 번째 상태에서 행동하면 홀수인 더미가 $1$개 이상 $N-2$개 이하가 되므로 두 패배 상태 중 어느 것도 될 수 없다.

두 번째 상태에서 모든 더미를 짝수로 만들려면 $N-1$개의 홀수 더미를 모두 골라야 하므로 불가능하다. 같은 종류의 상태로 이동하려면 유일한 짝수 더미와 홀수 더미 하나를 함께 골라야 한다. 그러면 기존의 최솟값이 $1$ 감소하여 홀수가 되고, 새로 짝수가 된 더미보다 작아진다. 따라서 새 유일한 짝수 더미가 최솟값일 수 없다. 즉, 패배 상태에서 다른 패배 상태로 이동할 수 없다.

이제 위 두 종류가 아닌 상태에서 패배 상태로 이동할 수 있음을 보이자.

• 홀수 더미가 $1$개 이상 $N-2$개 이하라면, 홀수 더미를 모두 골라 모든 더미를 짝수로 만든다.
• 모든 더미가 홀수라면, 최솟값인 더미 하나를 골라 유일한 짝수이자 최솟값으로 만든다.
• 홀수 더미가 $N-1$개이지만 유일한 짝수 더미가 최솟값이 아니라면, 그 짝수 더미와 최솟값인 홀수 더미를 고른다. 그러면 후자가 유일한 짝수이자 최솟값이 된다.

따라서 각 테스트 케이스에서 $O$, $M$, 돌의 합만 계산하면 된다. 시간 복잡도는 $O(N)$이고, 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT6