아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

컵과 콩

시간 제한1초메모리 제한256 MB

요약

1번부터 N-1번 컵에 콩이 담겨 있고 각 컵은 이동 범위 C_i를 가진다. 두 사람이 번갈아 콩 하나를 더 낮은 컵으로 옮기며, 옮길 콩이 없으면 지는 게임에서 승자를 판정한다.

난이도: 어려움10점 중 8점
유형: 게임 이론, 동적 계획법, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

0번부터 $N-1$ 번까지 번호가 붙은 $N$ 개의 컵이 있다. 각 $i$ ( $1 \leq i \leq N-1$ )에 대해 컵 $i$ 에는 콩이 $A_i$ 개 들어 있고, 이 컵에는 정수 $C_i$ 가 적혀 있다.

두 사람이 다음 게임을 한다.

각 차례에 플레이어는 0번 컵을 제외한 컵 하나를 골라 콩 하나를 집는다.
컵 $i$ 에서 콩을 집었다면, 그 콩을 컵 $i-C_i, \ldots, i-1$ 중 하나로 옮겨야 한다.
두 플레이어는 번갈아 가며 차례를 진행한다. 콩을 고를 수 없는 플레이어가 진다.

두 플레이어가 최선을 다해 플레이할 때 누가 이기는가?

입력

$N$
$C_1$ $A_1$
$C_2$ $A_2$
$\vdots$
$C_{N-1}$ $A_{N-1}$

출력

이긴 사람의 이름 "First" 또는 "Second"를 출력한다.

제한

$2 \leq N \leq 10^5$
$1 \leq C_i \leq i$
$0 \leq A_i \leq 10^9$
$A_i$ 중 적어도 하나는 0이 아니다.
입력의 모든 값은 정수이다.

힌트

예제 1에 대한 설명:

첫 번째 차례에 첫 번째 플레이어는 반드시 콩을 $2$ 에서 $1$ 로 옮겨야 한다.
두 번째 차례에 두 번째 플레이어는 반드시 콩을 $1$ 에서 $0$ 으로 옮겨야 한다.
세 번째 차례에 첫 번째 플레이어는 콩을 고를 수 없으므로 진다.

예제3

예제 1
입력
```
3
1 0
1 1
```
예상 출력
```
Second
```
예제 2
입력
```
7
1 1
2 0
1 0
2 0
4 1
3 0
```
예상 출력
```
First
```
예제 3
입력
```
7
1 1
2 0
1 9
2 10
4 3
3 5
```
예상 출력
```
Second
```

Loading...