| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 16 | 4 | 4 | 25.000% |
This is an interactive problem.
1804. Vice-president of the United States of America Aaron Burr challenged gubernatorial race candidate Alexander Hamilton for writing several offending pamphlets.
But Burr is sane enough to understand that, even if he kills Hamilton, he will lose his reputation and ruin his career. So, the enemies decided to simply play a game. To make everything more fair they decided to play it $g$ times.
Each game starts with Hamilton thinking up a positive integer $n$, and after that Burr tries to guess it. For any positive integer $x$ Burr may ask Hamilton about fraction of numbers between $1$ and $n$ inclusive that are divisible by $x$. In the other words, when asks a question about $x$, he receives the value of $$\frac{\left\lfloor\frac{n}{x}\right\rfloor}{n}.$$ Important detail is that Hamilton reports the answer to Burr as an irreducible fraction (here $\left\lfloor r \right\rfloor$ denotes the integral part of $r$).
Help Burr find the answer using some certain number of queries.
At the beginning your solution receives a single integer $g$ ($1 \leq g \leq 1000$), the number of games Hamilton and Burr are going to play.
For each test the number $q$ ($6 \leq q \leq 60$) is fixed, the maximum number of queries in a single game. It is guaranteed that $q$ queries are enough to solve the problem. This number is not available for your program, but it is mentioned in a scoring table below. If your program performs more than $q$ queries, it receives the "Wrong answer" verdict.
In order to perform a query you should output a line "X $t$" ($1 \leq t \leq 10^{18}$) where $t$ is a positive integer for which you want to know the value of $$\frac{\lfloor\frac{n}{t}\rfloor}{n}$$
As a result for a query your program receives two integers $a$ and $b$, the numerator and denominator of an irreducible fraction or number $-1$ in case you exceed the query limit.
If your program determines the number $n$, it should output a line "N $t$" where $t$ is the supposed answer ($1 \leq t \leq 10^{18}$). If the answer is correct, solution receives a line "Correct", otherwise it receives a line "Wrong".
After that the next game starts (if any of them left), otherwise solution should exit.
Note that in case you read $-1$ or line "Wrong" you must exit your programm immediately. Otherwise the verdict for your solution may be wrong, in particular you may receive Run-time error or Time limit exceeded!
It is guaranteed that in each case the $n$ numbers are fixed at the beginning of the game and they are not changed depending on your queries.
2 1 2 3 10 1 5 1 5 1 10 1 10 0 1 Correct 1 1 0 1 Correct
X 2 X 3 X 5 X 4 X 6 X 10 X 11 N 10 X 1 X 2 N 1
In the first sample case $g = 2$. The example queries are listed above, using results of these queries player may understand that in the first game the answer is $10$, and in the second game the answer is $1$.
Strictly follow the output format. After printing anything make sure to print a new line and to flush the output buffer, in order to do that you may use flush(output) for Pascal/Delphi, fflush(stdout) or cout.flush() for C/C++, sys.stdout.flush() for Python, System.out.flush() for Java.
Olympiad > Moscow Open Olympiad in Informatics > Moscow Open Olympiad in Informatics 2016-17 > Day 2 Panna Cotta번