CSES 7. Nim Game I (1730)

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

---

문제 설명

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes any number of 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 tt: the number of tests. After this, tt 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
3 5 6

출력 예

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

 

---

문제 풀이

Game Theory 에 나오는 Nim Game 

Nim Sum 을 계산해서, 0인 경우는 나중에 하는 플레이어가 이기게 되고 0이 아닌 경우는 먼저하는 플레이어가 이기는 승리전략이 존재한다. 따라서, 문제에서 플레이어가 이 전략을 알고 거기에 따라서 행동하기 때문에 Nim Sum을 계산하면 답을 찾을 수 있다. Nim Sum은 이진수로 표현했을때 각 자리수의 1들을 2개씩 짝지을 수 있으면 0 없으면 1로 계산하는 것이다. 즉, 값들을 bit XOR 를 하면 Nim Sum을 얻을 수 있다.

프로그램 내용

/// Nim sum == XOR values
...
	int tN, ret = 0;
	cin >> tN;

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

		ret ^= tmp;
...

 

7. Mathematics ( link )