問題一覧 > 通常問題

No.1588 Connection

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 118
作問者 : e869120e869120 / テスター : PCTprobabilityPCTprobability
3 ProblemId : 6693 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-08 22:48:20

問題文

この問題はインタラクティブ問題です。

$N$ 行 $N$ 列のマス目があり、上から $i$ 番目・左から $j$ 番目のマスを $(i, j)$ とします。

$M$ 個のマス $(x_1, y_1), (x_2, y_2), \cdots, (x_M, y_M)$ だけが黒く塗られており、その他のマスはすべて白く塗られています。特に、マス $(1, 1)$ とマス $(N, N)$ は必ず黒いです。

以下の質問を最大 $3000$ 回行うことで、マス $(1, 1)$ からマス $(N, N)$ まで黒色マス上を上下左右に移動してたどり着けるかを判定してください。

  • 整数 $a, b$ $(1 \leq a, b \leq N)$ を指定し、マス $(a, b)$ の色を聞く。

入出力

最初に、マス目の大きさ $N$ と黒いマスの数 $M$ を標準入力から受け取ってください。

$N$ $M$

次に、答えが分かるまで質問を繰り返してください。

質問は、以下の形式で標準出力に出力してください。

$a$ $b$

これは、あなたがマス $(a, b)$ を指定したことを意味します。ただし、$1 \leq a \leq N, 1 \leq b \leq N$ を満たさなければなりません。

これに対する応答は、次の形式で標準入力から与えられます。

$T$

ここで、$T$ は以下のいずれかの文字列です。

  • Black:マス $(a, b)$ は黒いマスである。
  • White:マス $(a, b)$ は白いマスである。
  • -1:質問回数が $3000$ 回を超えた、または不正な出力を行った。
ジャッジが応答 -1 を返した場合、提出はすでに不正解とみなされています。この場合、プログラムをすぐに終了させてください。

最後に、答えが分かったら、解答を以下の形式で標準出力に出力してください。

(☆)マス $(1, 1)$ からマス $(N, N)$ までたどり着ける場合

Yes

(★)マス $(1, 1)$ からマス $(N, N)$ までたどり着けない場合

No

制約

  • $2 \leq N \leq 500$
  • $2 \leq M \leq 1000$
  • マス $(1, 1)$ とマス $(N, N)$ は黒く塗られている
  • $N, M$ は整数

注意

  • 不正な出力をした時の挙動は WA とは限りません。(RE などになる可能性もあります)

サンプル

例えば、$N = 2, M = 3$ でマス $(1, 1), (1, 2), (2, 2)$ が黒い場合、以下のようなやり取りが考えられます。

Input Output
2 3
1 1
Black
1 2
Black
2 1
White
2 2
Black
Yes

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