問題一覧 > 通常問題

No.1801 Segment Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : NatsubiSoganNatsubiSogan / テスター : first_vilfirst_vil penguinmanpenguinman
24 ProblemId : 7064 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-20 01:15:09

問題文

二次元平面上に、$4$ 点 $(0,0), \ (0,H), \ (W,0), \ (W,H)$ を頂点とする長方形があります。

Natsubi くんと Sogan くんがこの長方形を使ってゲームをします。Natsubi くんから始めて、交互に以下の操作を行います。

  • 距離が $D$ 以下 であるような、相異なる 長方形の 周上の 格子点($x$ 座標と $y$ 座標がともに整数である点)$(x_1,y_1), \ (x_2,y_2)$ を選び、$(x_1,y_1)$ と $(x_2,y_2)$ を結ぶ線分を平面上に書き入れる。
  • ただし、その線分は、既に書かれている線分のいずれとも、長方形内部(周上を含む)で 共有点を持たない ようにしなければならない。

先に操作を行えなくなった方が負けです。両者が最善を尽くしたとき、勝利するのはどちらでしょうか?

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

入力の $1$ 行目に、テストケースの数 $T$ が以下の形式で与えられる。

$T$

そして、$T$ 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。

$H$ $W$ $D$
  • 入力はすべて整数
  • $1 \leq T \leq 10^5$
  • $1 \leq H,W,D \leq 10^9$

出力

$T$ 行出力してください。

$i \ (1 \leq i \leq T)$ 行目には、$i$ 番目のテストケースについて、勝利するのが Natsubi くんなら N と、Sogan くんなら S と出力してください。

最後に改行してください。

サンプル

サンプル1
入力
5
1 1 2
1 1 1
31 41 59
26 53 58
97 93 23
出力
N
S
N
N
S
  • $1$ 番目のケース:Natsubi くんが $(0,0),\ (1,1)$ を結ぶ線分を書くと、Sogan くんが引ける線分はなくなります。よって、Natsubi くんが必勝です。
  • $2$ 番目のケース:$(0,0),\ (1,1)$ を結ぶ線分は長さ $\sqrt{2} \ (>1)$ なので選ぶことが出来ません。例えば Natsubi くんが $(0,0),\ (0,1)$ を結ぶ線分を書いたとすると、Sogan くんは $(1,0),\ (1,1)$ を結ぶ線分を書くしかありません。すると、次に Natsubi くんが書ける線分はなくなります。よって、Sogan くんが勝ちます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。