레이팅 미적용농부 존과 그의 숙적 농부 노즈(Nhoj)는 원형 헛간에서 게임을 하고 있다. 헛간에는 \(N\)개(\(1 \leq N \leq 10^5\))의 방이 있고, \(i\)번째 방에는 처음에 소가 \(a_i\)마리(\(1 \leq a_i \leq 5\cdot 10^6\)) 있다. 게임은 다음과 같이 진행된다.
- 두 농부는 항상 같은 방에 있다. 방에 들어간 후, 농부 존이 먼저 시작하여 각 농부는 정확히 한 번씩 차례를 가진다. 두 농부는 처음에 방 \(1\)에 들어간다.
- 현재 방에 소가 한 마리도 없으면, 차례인 농부가 진다. 그렇지 않으면, 차례인 농부는 정수 \(P\)를 고르는데, \(P\)는 \(1\)이거나 현재 방에 있는 소의 수 이하의 소수여야 하며, 현재 방에서 소 \(P\)마리를 내보낸다.
- 두 농부가 모두 차례를 마치면, 두 농부는 원형 헛간의 다음 방으로 이동한다. 즉, 농부들이 방 \(i\)에 있으면 방 \(i+1\)로 이동하되, 방 \(N\)에 있는 경우에는 방 \(1\)로 이동한다.
두 농부가 모두 최적으로 플레이할 때 게임에서 이기는 농부를 구하시오.
출제: Chongtian Ma, Jesse Choe, and Yuval Vaknin
배점
- 입력 2-4는 \(N=1\)을 만족한다.
- 입력 1, 2, 5-7은 \(a_i\le 1000\)을 만족한다.
- 입력 8-20은 추가 제약이 없다.
출제: Chongtian Ma, Jesse Choe, and Yuval Vaknin
입력은 \(T\)개의 테스트 케이스로 이루어진다. 첫째 줄에 \(T\) (\(1 \leq T \leq 1000\))가 주어진다. 이어서 \(T\)개의 테스트 케이스가 주어진다.
각 테스트 케이스는 \(N\)이 주어지는 줄로 시작하며, 다음 줄에 \(a_1,\dots,a_N\)이 주어진다.
모든 \(N\)의 합이 \(2\cdot 10^5\) 이하임이 보장된다.
각 테스트 케이스에 대해 게임에서 이기는 농부를 "Farmer John" 또는 "Farmer Nhoj"로 출력한다.
5
1
4
1
9
2
2 3
2
7 10
3
4 9 4Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer NhojFor the first test case, Farmer John can remove \(1\), \(2\), or \(3\) cows from the
first room. Whichever number he removes, Nhoj can remove the remaining cow(s),
forcing FJ to lose when they circle back to the first room.
For the second test case, FJ can remove \(5\) cows, forcing Nhoj to work with only
\(4\) cows remaining. Now, Nhoj can either remove \(1\), \(2\), or \(3\) cows. This is
now similar to the first test case.
For the third and fourth test cases, FJ can immediately remove all the cows from
the first room, forcing Nhoj to lose.
For the fifth test case, FJ can remove \(1\), \(2\), or \(3\), cows from the first
room, and Nhoj can remove the rest right after. When they circle back around to
the first room, FJ will lose.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Silver