CSES 7. Nim Game II (1098)

출처: https://cses.fi/problemset/task/1098

---

문제 설명

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

입력 

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... x_n : the number of sticks in each heap.

출력

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

입력 예

3
4
5 7 2 5
2
4 1
3
4 4 4

출력 예

first
first
second

제약조건

• 1 <= t <= 2*1e5
• 1 <= n <= 2*1e5
• 1 <= x_i <= 1e9 
• the sum of all n is at most 2*1e5 

---

문제 풀이

Nim Game의 변형문제이다.

제외할 수 있는 숫자가 1~k개로 제한되는 경우에는 (k+1) modulo 결과를 Nim Sum 이라고 한다.

• Nim Sum == 0 : 나중에 하는 사람이 승리하는 전략이 존재
• Nim Sum != 0 : 먼저하는 사람이 승리하는 전략이 존재

대항해시대4의 경우에 동전을 제거하는 게임이 나오는데 같은 원리를 적용하면, 승리할 수 있다. (컴퓨터가 이 전략을 적용하기 때문에 최초에 남는 동전에 따라 게임 결과가 정해져 있다고 생각하면 된다.) 

프로그램 내용

/// (1~k) substraction game
/// Nim sum == XOR values of (value % (k+1))

...
	int tN, ret = 0;
	cin >> tN;

	for(int id=0; id<tN;++id)
		int tmp;
		cin >> tmp;

		ret ^= (tmp%MAX_R);
...        

 

7. Mathematics ( link )