No.1588 Connection
タグ : / 解いたユーザー数 136
作問者 :
e869120
/ テスター :
PCTprobability
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.
-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 beREor 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もしくは右上の雲マークをクリックしてアカウントを作成してください。