CSES 7. Stair Game(1099)

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

---

문제 설명

There is a staircase consisting of n stairs, numbered 1,2,…,n. Initially, each stair has some number of balls.

There are two players who move alternately. On each move, a player chooses a stair kk where k≠1 and it has at least one ball. Then, the player moves any number of balls from stair k to stair k−1. The winner is the player who moves last.

Your task is to find out who wins the game when both players play optimally.

입력  

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

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

The next line has n integers p_1,p_2,…,p_n : the initial number of balls on each stair.

출력 

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

입력 예

3
3
0 2 1
4
1 1 1 1
2
5 3

출력 예

first
second
first

제약조건

• 1 <= nT <= 2x10^5
• 1 <= tN <= 2x10^5
• 1 <= p_i <= 10^9
•  sum of all n is at most 2x10^5

---

문제 풀이 

Nim Game ( link ) 의 변형 문제이다. 

아래에 있는 계단부터 마지막 계단까지 1 ~ N 으로 번호를 붙였을때, 마지막으로 볼이 남아있는 계단을 선택하는 사람이 승리하게 된다.

 

Nim 게임에서는 선택한 것을 제거하는데, 이 게임에서는 아래로 옮길 수 있.으므로 게임속에서 계속 남아 있게 된다.

 

단, 첫번째 계단 (1번 계단) 은 선택할 수 없기 때문에 계단2에서 계단 1로 옮기는 경우가 볼을 제거하는 것과 같은 효과를 가진다. 즉, 2번째 계단에 마지막으로 볼이 남아 있을때가 게임이 끝나는 순간이 된다.  그러므로, 짝수 계단에 있는 볼들을 대상으로 Nim Sum을 계산해보면 게임의 승자를 알 수 있게 된다.

프로그램 내용

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

	for(int id=0; id<tN;++id)
    	int tmp;
		cin >> tmp;
        if(id & 1)
			ret ^= tmp;
...

 

Mathematics  ( link )