| Author: | A. Usmanov | Time limit: | 1 sec | |
| Input / output: | interactive | Memory limit: | 256 Mb |
If you have already read the problem statement H. Hard banknote thrower: the task specification for this problem differs only in the operation performed by the banknote thrower. Namely: addition operation instead of bitwise multiplication operation.
Oleg has been using the services of Moneykoff Bank for a long time. Today, he needs to throw a large sum of money from his card, but he forgot its PIN code. Fortunately for the company, Moneykoff Bank's banknote throwers can provide hints about the PIN code.
Firstly, the banknote thrower reports the result of comparing neighboring digits in the PIN code.
For example, for the PIN code 0911, it would be <>=, and for the popular PIN code 1234, it would be <<<.
Secondly, you can attempt to input a PIN code into the banknote thrower. If it proves incorrect, the banknote thrower will perform the operation: addition of the correct and entered PIN codes, and report the result of comparing adjacent digits in the resulting number. Of course, after such an operation, the number of digits may be greater than in the original PIN code. The Moneykoff Bank programmers have anticipated such overflow: if new digits appear, a comparison of neighboring digits will also be performed for them. For user safety, after 10 attempts to enter the wrong PIN code, the card is blocked.
Help Oleg determine the PIN code for the card before it is blocked.
This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.
First, the jury's program sends your program an integer N — the number of digits in the PIN code.
Then, on a new line, a string of N − 1 characters <, > and = — comparing neighboring digits in the PIN code.
After that, your program can make queries of the form "? X",
where X is an integer, an attempt to enter a PIN code, and can be output without leading zeros.
If the PIN code is correct, the jury's program responds to your program with the string "ok",
after which your program must terminate.
Otherwise, the jury's program responds with a string of at least N − 1 characters <, > and = —
comparing neighboring digits in the result of
addition
of the correct and entered PIN codes.
Your program can only make 9 queries with an incorrect PIN code. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.
Every query must be a single line ending with single end-of-line (\n).
Output buffers must be flushed after every line:
| Language | C++ | Pascal | Java | Python |
| Code | cout.flush() |
flush(output) |
System.out.flush() |
stdout.flush() |
If your program makes incorrect query, it will receive "Presentation error" verdict.
If your program receives the string "-1" from the jury's program, it must immediately terminate.
This is possible if your program violates the interaction protocol.
If your program does not terminate, the verdict may differ from those described above (for example, it may be "Runtime error").
2 ≤ N ≤ 18
0 ≤ X < 10N
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
Давайте попробуем прийти к состоянию, когда загаданное число X и то,
что мы прибавляем Y, даёт сумму состоящую из одинаковых цифр,
то есть когда ответ программы жюри будет состоять из символов =.
Для этого будем постепенно наращивать Y в тех позициях,
в которых в сумме гарантированно не находятся максимальные цифры,
так как увеличение в этом месте может привести к переполнению суммы.
Найти не максимумы (или минимумы) можно за линейный проход по строке сравнения.
Это будут числа не находящиеся внутри сравнений <==...==>,
а также не находящиеся внутри сравнений ...==> и <==...
для начала и конца строки сравнения соответственно.
После того, как пришли к сумме состоящей из одинаковых цифр, необходимо понять что это за цифра. Для этого можно продолжить увеличивать в Y все разряды, пока не случится переполнения. Если оно случилось, то значит на предыдущей итерации сумма состояла из девяток. Если переполнения не случилось за 9 запросов, то значит, что на текущей итерации сумма состоит из девяток, так как при нашей логике увеличения Y за такое количество запросов все цифры в сумме должны были дойти до значения 9. И в том и в другом случае можно легко вычислить X через Y.