No.3519 A/B Problem
Problem Statement
This is a reactive problem (your program must run interactively with the judge's program).
Division-Loving bot is a bot that loves division.
Division-Loving bot secretly holds a non-negative integer $A$ and a positive integer $B$, and wants to know $\lfloor A/B \rfloor$, the largest integer not exceeding the fraction $A/B$ obtained by dividing $A$ by $B$.
To this end, first the non-negative integer $a$ is set to $A$, and then you perform the following sequence of exchanges (hereafter called a query) any number of times between $0$ and $1000$, inclusive.
- First, you choose non-negative integers $n, m$ not greater than $10^{100}$, and ask for the order relation between $na$ and $mB$.
- Next, Division-Loving bot tells you the order relation between $na$ and $mB$.
- Finally, if $na \geq mB$, $a$ is updated by replacing it with $na - mB$.
After that, find $\lfloor A/B \rfloor$.
Input and Output
First, make queries any number of times between $0$ and $1000$, inclusive. A query is made through standard input and output in the following format:
- First, choose non-negative integers $n, m$ not greater than $10^{100}$, and print
?and $n, m$ separated by half-width spaces on $1$ line. - Then, you are given
>if $na > mB$,=if $na = mB$, and<if $na < mB$.
? $n$ $m$
Next, print your answer to this problem to standard output in the following format:
- Print
!and $\lfloor A/B \rfloor$ separated by a half-width space on $1$ line.
! $\lfloor A/B \rfloor$
Finally, print a newline.
Constraints
Although not given in the input, $A, B$ satisfy the following constraints:
- $A, B$ are fixed before all queries. That is, the values of $A, B$ do not change across queries.
- $A$ is an integer satisfying $0 \leq A \leq 10^{100}$.
- $B$ is an integer satisfying $1 \leq B \leq 10^{100}$.
The input satisfies the following constraint:
- For any non-negative integers $n, m$ not greater than $10^{100}$, the input given in response to asking for the order relation between $na$ and $mB$ is one of the characters
>,=,<.
Notes
If you are not familiar with reactive problems, please also refer to the summary of reactive problems.
In 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, add a newline at the end and flush standard output.
- Terminate your program immediately after printing your answer to this problem.
Sample
The following is an example of the interaction when Division-Loving bot secretly holds $(A,B) = (70,9)$.
Initially, $a = A = 70$.
| Input | Output | Explanation |
|---|---|---|
? 13 100 |
You asked for the order relation between $13a$ and $100B$. | |
> |
Division-Loving bot answered that $13a = 910$ is greater than $100B = 900$. Since $13a \geq 100B$, $a$ is updated by replacing it with $13a - 100B = 910 - 900 = 10$. | |
? 11 20 |
You asked for the order relation between $11a$ and $20B$. | |
< |
Division-Loving bot answered that $11a = 110$ is less than $20B = 180$. Since $11a \geq 20B$ does not hold, $a$ is not updated. | |
? 9 10 |
You asked for the order relation between $9a$ and $10B$. | |
= |
Division-Loving bot answered that $9a = 90$ is equal to $10B = 90$. Since $9a \geq 10B$, $a$ is updated by replacing it with $9a - 10B = 90 - 90 = 0$. | |
! 7 |
You answered that $\lfloor A/B \rfloor$ is $7$. This is correct. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。