問題一覧 > 通常問題

No.3161 Find Presents

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 45
作問者 : jastaway / テスター : 👑 みうね fluorine 👑 kencho TKTYI kmmtkm tatesoto butsurizuki
お気に入りにしたユーザー ProblemId : 12235 / 自分の提出
問題文最終更新日: 2025-05-23 19:01:18
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
KCPC新歓杯 -Happy Birthday physics0523- (順位表) の他の問題:

Problem Statement

Butsurizuki-kun received many presents for his birthday, but he has lost them somewhere on a 2D plane.

You have a machine that, given a range, determines whether a present exists in that range.

However, running the machine has a cost, so please find all of Butsurizuki-kun's presents within a limited number of uses.

This is an interactive problem (a problem in which your program and the judge system communicate through input and output).

The judge is not adaptive. For each test case, the number and positions of the presents are fixed before your program runs and do not change.

There are $N$ points on a 2D plane, and the coordinates of the $i$-th point are $(X_i, Y_i)$. However, $N, X_i, Y_i$ are not given to you; the judge system keeps these values hidden.

You may ask the judge system the following question up to $8000$ times.

  • Choose integers $x_l, x_r, y_l, y_r$ between $0$ and $10^6$, inclusive. They must satisfy $0 \leq x_l \leq x_r \leq 10^6, 0 \leq y_l \leq y_r \leq 10^6$. Then ask whether there exists an integer $i$ between $1$ and $N$, inclusive, such that $x_l \leq X_i \leq x_r$ and $y_l \leq Y_i \leq y_r$.

Determine $N$ and the set $\{ (X_i, Y_i) \}$ using at most $8000$ questions.

Constraints

  • $1 \leq N \leq 100$
  • $0 \leq X_i, Y_i \leq 10^6$
  • $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$
  • $N, X_i, Y_i$ are all integers.

Input and Output

This is an interactive problem (a problem in which your program and the judge system communicate through input and output).

Initially, nothing is given as input.

Repeat the following question between $0$ and $8000$ times, inclusive.

For a question, letting the chosen range on the 2D plane be $[x_l, x_r + 1)\times[y_l, y_r + 1)$, print to standard output in the following format, using integers $x_l, x_r, y_l, y_r$ $(0 \leq x_l \leq x_r \leq 10^6, 0 \leq y_l \leq y_r \leq 10^6)$.

? $x_l\ x_r\ y_l\ y_r$

Then, if there exists an integer $i$ between $1$ and $N$, inclusive, such that $x_l \leq X_i \leq x_r$ and $y_l \leq Y_i \leq y_r$, you are given

1

and if no such integer exists, you are given

0

from standard input in the format above.

However, if the question is invalid, -1 is given from standard input.

-1

Specifically, this is given if at least one of the following holds:

  • The printed $x_l, x_r, y_l, y_r$ do not satisfy the constraints.
  • You asked more than $8000$ questions.

In this case, your answer has already been determined to be incorrect, so terminate your program immediately.

Finally, answer with the number of presents $N$ and the set of positions ${ (X_i, Y_i) }$ by printing $N+1$ lines to standard output in the following format.

! $N$
$X_1\ Y_1$
$X_2\ Y_2$
  $\vdots$
$X_N\ Y_N$

More precisely, first print ! and the number of presents $N$ separated by a space on the first line, followed by a newline.

! $N$

Then, on line number $i + 1$ $(1 \leq i \leq N)$, print the position $X_i, Y_i$ of the $i$-th present separated by a space, followed by a newline.

$X_i\ Y_i$

Here, $(X_i, Y_i) \neq (X_j, Y_j)$ must hold for every pair of integers $1 \leq i < j \leq N$.

Your answer is considered correct if ${ (X_i, Y_i) }$ matches the answer as a set, so the order of the presents' positions does not affect the judge result.

After this output, terminate your program immediately.

For all output, your program is also considered incorrect if the output does not follow the specified format. In that case -1 is returned, so terminate your program immediately in that case as well.

Notes

  • Each time you print output, end it with a newline and flush standard output. Otherwise, the judge result may be TLE or WA.
  • After printing your answer (or receiving -1), terminate your program immediately. Otherwise, the judge result is undefined.
  • Note that extra newlines may be treated as output in an invalid format.
  • The judge system for this problem is not adaptive. That is, for each test case, the number and positions of the presents are fixed before your program runs and do not change.

Sample Input and Output

In this example, $N=3, { (X_i, Y_i) } = { (1, 1), (2, 2), (5, 5) }$.

InputOutputExplanation
? 0 3 0 3Asks whether a present exists in the range $ [0, 3+1)\times [0, 3+1)$.
1Since $(1, 1), (2, 2)$ are in the above range, $1$ is returned as the response.
? 3 4 3 4Asks whether a present exists in the range $ [3, 4+1)\times [3, 4+1)$.
0Since no present is in the above range, $0$ is returned as the response.
? 1 1 1 1Asks whether a present exists in the range $ [1, 1+1)\times [1, 1+1)$.
1Since $(1, 1)$ is in the above range, $1$ is returned as the response.
? 4 5 0 5Asks whether a present exists in the range $ [4, 5+1)\times [0, 5+1)$.
1Since $(5, 5)$ is in the above range, $1$ is returned as the response.
! 3Outputs the answer that there are $3$ presents. The positions are printed from the next line.
5 5Answers that there is a present at $(5, 5)$.
1 1Answers that there is a present at $(1, 1)$.
2 2Answers that there is a present at $(2, 2)$.
The above questions alone do not determine the number and positions of the presents, but since the judge is not adaptive, this is considered correct.
The order of the presents' coordinates does not matter.

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