No.2753 Pigeonhole Principle
タグ : / 解いたユーザー数 60
作問者 : 👑
Moss_Local
Problem Statement
This is a reactive problem (your program must run interactively with the judge's program).
At the beginning of the input, an integer $N$ greater than or equal to $2$ is given.
Pigeonhole-Loving Bot is a bot that loves pigeonholes.
Pigeonhole-Loving Bot owns $N$ pigeonholes, numbers them with the positive integers $i$ less than or equal to $N$, calls each one pigeonhole $i$, and cherishes them.
However, some pigeons have settled in each of the $N$ pigeonholes. You do not know how many pigeons have settled in which pigeonhole, but you have obtained the following information from Pigeonhole-Loving Bot.
- For each positive integer $i$ less than $N$, the number of pigeons living in pigeonhole $i$ is a positive integer less than or equal to the number of pigeons living in pigeonhole $i+1$.
- The number of pigeons living in pigeonhole $N$ is a positive integer less than $N$.
Based on this information, you have guessed that there may exist $2$ distinct pigeonholes in which equal numbers of pigeons live.
Therefore, you perform the following exchange exactly $10$ times.
- You choose a positive integer $i$ less than or equal to $N$ and ask Pigeonhole-Loving Bot how many pigeons live in pigeonhole $i$. (You may ask again even if you have already asked and know the answer.)
- Pigeonhole-Loving Bot tells you how many pigeons live in pigeonhole $i$.
After that, determine whether there exist $2$ distinct pigeonholes in which equal numbers of pigeons live, and if they exist, find $1$ pair of such pigeonholes.
Input and Output
For each positive integer $q$ less than or equal to $10$, let $i_q$ denote the positive integer you choose in the $q$-th exchange.
First, the number $N$ of pigeonholes is given from standard input in $1$ line.
$N$
After that, perform exactly $10$ exchanges. For each positive integer $q$ less than or equal to $10$, the $q$-th exchange is performed using standard input and output in the following format:
- First, output
?and $i_q$ separated by a single space in $1$ line (as line $q$ of the entire output).
? $i_q$
(鳩の巣 $i_q$ に住み着いている鳩の数)
Finally, output your answer to this problem to standard output in the following format:
- If there do not exist $2$ distinct pigeonholes in which equal numbers of pigeons live, output
No(as line $11$ of the entire output).
No
Yes and $i,j$ separated by single spaces (as line $11$ of the entire output).Yes $i$ $j$
Print a newline at the end.
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $2 \leq N \leq 10^3$.
- The input in the $10$ exchanges is consistent with the following information stated in the problem statement, and the number of pigeons living in each pigeonhole does not change before or after the exchanges.
- For each positive integer $i$ less than $N$, the number of pigeons living in pigeonhole $i$ is a positive integer less than or equal to the number of pigeons living in pigeonhole $i+1$.
- The number of pigeons living in pigeonhole $N$ is a positive integer less than $N$.
Notes
If you are not familiar with reactive problems, please also refer to the summary of reactive problems.
For this problem, the judge result is not guaranteed for submissions that do not follow the instructions below:
- Strictly follow the specified output format. For example, do not insert extra spaces.
- Each time you output, end it with a newline and flush standard output.
- Terminate your program immediately after outputting your answer to this problem.
Sample
| Input | Output | Explanation |
|---|---|---|
? 1 |
You asked for the number of pigeons living in pigeonhole $1$. | |
1 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $1$ is $1$. | |
? 2 |
You asked for the number of pigeons living in pigeonhole $2$. | |
2 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $2$ is $2$. | |
? 3 |
You asked for the number of pigeons living in pigeonhole $3$. | |
3 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $3$ is $3$. | |
? 4 |
You asked for the number of pigeons living in pigeonhole $4$. | |
4 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $4$ is $4$. | |
? 5 |
You asked for the number of pigeons living in pigeonhole $5$. | |
5 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $5$ is $5$. | |
? 6 |
You asked for the number of pigeons living in pigeonhole $6$. | |
6 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $6$ is $6$. | |
? 7 |
You asked for the number of pigeons living in pigeonhole $7$. | |
7 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $7$ is $7$. | |
? 8 |
You asked for the number of pigeons living in pigeonhole $8$. | |
8 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $8$ is $8$. | |
? 9 |
You asked for the number of pigeons living in pigeonhole $9$. | |
9 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $9$ is $9$. | |
? 10 |
You asked for the number of pigeons living in pigeonhole $10$. | |
9 |
Pigeonhole-Loving Bot answered that the number of pigeons living in pigeonhole $10$ is $9$. | |
Yes 9 10 |
You found that the number of pigeons living in pigeonhole $9$ and the number of pigeons living in pigeonhole $10$ are equal, so you answered accordingly. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。