8060 : 님 게임
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$n$개의 돌 더미가 있고, 각 더미에는 일정한 개수의 돌이 있습니다. 두 명의 플레이어가 번갈아가며 게임을 진행합니다.
자신의 차례가 되면 하나의 돌 더미를 선택해 $1$개 이상의 돌을 제거할 수 있습니다. 마지막 돌을 제거하는 사람이 게임에서 승리합니다. (즉, 더 이상 돌을 가져갈 수 없는 사람이 패배합니다.)
두 플레이어가 최적의 전략으로 게임에 임할 때, 첫 번째 플레이어가 이기는지, 두 번째 플레이어가 이기는지 판정하십시오.
[제약 조건]
• $1 \le t \le 100$
• $1 \le n \le 200{,}000$ (모든 테스트 케이스의 $n$의 합 $\le 200{,}000$)
• $1 \le x_i \le 10^9$
자신의 차례가 되면 하나의 돌 더미를 선택해 $1$개 이상의 돌을 제거할 수 있습니다. 마지막 돌을 제거하는 사람이 게임에서 승리합니다. (즉, 더 이상 돌을 가져갈 수 없는 사람이 패배합니다.)
두 플레이어가 최적의 전략으로 게임에 임할 때, 첫 번째 플레이어가 이기는지, 두 번째 플레이어가 이기는지 판정하십시오.
[제약 조건]
• $1 \le t \le 100$
• $1 \le n \le 200{,}000$ (모든 테스트 케이스의 $n$의 합 $\le 200{,}000$)
• $1 \le x_i \le 10^9$
입력 설명
첫째 줄에 테스트 케이스의 개수 $t$가 주어집니다. ($1 \le t \le 100$)
각 테스트 케이스는 두 줄로 구성됩니다:
- 첫째 줄에 돌 더미의 개수 $n$이 주어집니다. ($1 \le n \le 200{,}000$)
- 둘째 줄에 각 더미의 돌 개수 $x_1, x_2, \dots, x_n$이 공백으로 구분되어 주어집니다. ($1 \le x_i \le 10^9$)
모든 테스트 케이스의 $n$의 합은 $200{,}000$을 초과하지 않습니다.
각 테스트 케이스는 두 줄로 구성됩니다:
- 첫째 줄에 돌 더미의 개수 $n$이 주어집니다. ($1 \le n \le 200{,}000$)
- 둘째 줄에 각 더미의 돌 개수 $x_1, x_2, \dots, x_n$이 공백으로 구분되어 주어집니다. ($1 \le x_i \le 10^9$)
모든 테스트 케이스의 $n$의 합은 $200{,}000$을 초과하지 않습니다.
출력 설명
각 테스트 케이스에 대해 첫 번째 플레이어가 이기면
first, 두 번째 플레이어가 이기면 second를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
4
5 7 2 5
2
2 2
3
1 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
first
second
second도움
스프라그-그룬디 정리에 의해, 님 게임의 각 상태의 그룬디 값은 각 더미 돌 개수들의 XOR 합(Nim-sum) $S = x_1 \oplus x_2 \oplus \dots \oplus x_n$과 같습니다. $S \neq 0$인 경우 선공(first)의 필승 상태이고, $S = 0$인 경우 후공(second)의 필승 상태입니다.