No.1801 Segment Game
タグ : / 解いたユーザー数 110
作問者 :
penguinman
Problem Statement
On a two-dimensional plane, there is a rectangle with the $4$ points $(0,0), \ (0,H), \ (W,0), \ (W,H)$ as its vertices.
Natsubi and Sogan play a game using this rectangle. Starting with Natsubi, they alternately perform the following operation.
- Choose points $(x_1,y_1), \ (x_2,y_2)$ whose distance is at most $D$ and which are distinct on the perimeter lattice points (points whose $x$ and $y$ coordinates are both integers) of the rectangle, and draw the segment connecting $(x_1,y_1)$ and $(x_2,y_2)$ on the plane.
- However, the segment must not share any point with any of the already drawn segments inside the rectangle (including its perimeter).
The player who first becomes unable to perform the operation loses. When both players play optimally, which of them wins?
You are given $T$ test cases; find the answer for each of them.
Input
On line $1$ of the input, the number of test cases $T$ is given in the following format.
$T$
Then, $T$ test cases follow. Each of them is given in the following format.
$H$ $W$ $D$
- All input values are integers.
- $1 \leq T \leq 10^5$
- $1 \leq H,W,D \leq 10^9$
Output
Print $T$ lines.
On line $i \ (1 \leq i \leq T)$, print N if Natsubi wins the $i$-th test case, and S if Sogan wins it.
Print a newline at the end.
Sample
Sample 1
Input
5 1 1 2 1 1 1 31 41 59 26 53 58 97 93 23
Output
N S N N S
- Case $1$: If Natsubi draws the segment connecting $(0,0),\ (1,1)$, Sogan has no segment left to draw. Therefore, Natsubi has a winning strategy.
- Case $2$: The segment connecting $(0,0),\ (1,1)$ has length $\sqrt{2} \ (>1)$, so it cannot be chosen. For example, if Natsubi draws the segment connecting $(0,0),\ (0,1)$, Sogan has no choice but to draw the segment connecting $(1,0),\ (1,1)$. Then, Natsubi has no segment left to draw. Therefore, Sogan wins.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。