問題一覧 > 通常問題

No.1588 Connection

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 136
作問者 : e869120 / テスター : PCTprobability
お気に入りにしたユーザー ProblemId : 6693 / 自分の提出
問題文最終更新日: 2021-07-08 22:48:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 303 (順位表) の他の問題:

Problem Statement

This is an interactive problem.

There is a grid with $N$ rows and $N$ columns. Let $(i, j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.

Only the $M$ cells $(x_1, y_1), (x_2, y_2), \cdots, (x_M, y_M)$ are painted black, and all other cells are painted white. In particular, cells $(1, 1)$ and $(N, N)$ are always black.

By asking the following query at most $3000$ times, determine whether it is possible to reach cell $(N, N)$ from cell $(1, 1)$ by moving up, down, left, and right through black cells.

  • Specify integers $a, b$ $(1 \leq a, b \leq N)$ and ask for the color of cell $(a, b)$.

Input and Output

First, receive the grid size $N$ and the number of black cells $M$ from standard input.

$N$ $M$

Next, repeat queries until you know the answer.

Print each query to standard output in the following format.

$a$ $b$

This means that you specify cell $(a, b)$. Here, $1 \leq a \leq N, 1 \leq b \leq N$ must be satisfied.

The response to this is given from standard input in the following format.

$T$

Here, $T$ is one of the following strings.

  • Black: Cell $(a, b)$ is a black cell.
  • White: Cell $(a, b)$ is a white cell.
  • -1: The number of queries exceeded $3000$, or you produced invalid output.
If the judge returns the response -1, your submission has already been judged as incorrect. In this case, terminate your program immediately.

Finally, once you know the answer, print it to standard output in the following format.

(☆) If it is possible to reach cell $(N, N)$ from cell $(1, 1)$:

Yes

(★) If it is not possible to reach cell $(N, N)$ from cell $(1, 1)$:

No

Constraints

  • $2 \leq N \leq 500$
  • $2 \leq M \leq 1000$
  • Cells $(1, 1)$ and $(N, N)$ are painted black
  • $N, M$ are integers

Notes

  • The verdict for invalid output is not necessarily WA. (It may also be RE or something else.)

Sample

For example, if $N = 2, M = 3$ and cells $(1, 1), (1, 2), (2, 2)$ are black, the following interaction is possible.

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

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