시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 51 | 0 | 0 | 0.000% |
This is an interactive problem.
Alice has a black box which works with integers modulo $m = 10^{9} + 7$. If a user types a number $x$ on the keyboard of the box, the screen shows the number equal to the value of the polynomial $p (x) = (a_{d} x^{d} + a_{d - 1} x^{d - 1} + \ldots + a_{1} x^{1} + a_{0}) \bmod m$. The degree $d$ of the polynomial is unknown, as are its coefficients $a_{i}$. It is only known that $0 \le d \le 10$ and $a_d \ne 0$.
Alice can type several numbers $x$ and learn the values of the polynomial for these numbers. Help her find the degree $d$ of the polynomial. She can input an $x$ at most $d + 3$ times.
To learn the value of the polynomial for number $x$, print a line of the form "ask
$x$" ($0 \le x < 10^{9} + 7$). As a result, you will get a line with the value $p (x)$, or, if you asked more than $d + 3$ such questions, you will get the number $-1$ instead of the value, and evaluation of your solution will terminate.
To give the answer, print a line of the form "degree
$d$". After that, terminate your solution gracefully.
After printing each line, flush the output buffer, or you will get the outcome Idleness Limit Exceeded
: this can be done by calling, for example, fflush (stdout)
in C or C++, System.out.flush ()
in Java, flush (output)
in Pascal, or sys.stdout.flush ()
in Python.
1000000006 7 34 98
ask 1 ask 3 ask 6 ask 10 degree 2
In each test, the degree and the coefficients of the polynomial $p (x)$ are chosen and fixed in advance.
In the example, which is also the first test in the testing system, $p (x) = x^2 + 1\,000\,000\,005$. All other tests were created as follows: first, the degree $d$ was chosen ($0 \le d \le 10$), and after that, one of the polynomials of such degree was chosen as $p (x)$ uniformly at random.