Problem A
Botched Sequence of Tyrfingur
Tyrfingur maintains his data in a very eccentric fashion. Instead of storing his sequence of numebrs in one increasing row he has appointed one value as the main value. Next he makes the main value point to one value that’s smaller and one value that’s bigger and makes them belong to the main value. For each value under the main value he does the same, but if nothing exists that is smaller (or bigger), the value will simply point to nothing. If a value $x$ points to a smaller value $y$ then all values belonging to $y$ are smaller than $x$. If a value $x$ points to a larger value $y$ then all values belonging to $y$ are bigger than $x$. Note that if $z$ belongs to $y$ and $y$ belongs to $x$ then $z$ belongs to $x$.
You have been tasked with figuring out what the sorted sequence of numbers Tyrfingur has is. The problem is Tyrfingur never wrote it down, just keeping it in his head. Thus you have to ask him questions over and over to get the information step by step. Furthermore the sequence itself is private data and you can not see it. Thus you have to instruct Tyrfingur on how to write the sequence down on paper in inceasing order. He then puts the paper in an envelope and seals it before handing it over to you.
At the start Tyrfingur is thinking about the main value and you can instruct him by asking him to write down the value he is thinking of, to think of the smaller value it points to, to think of the larger value it points to or to go back and think of the value that pointed to what he’s currently thinking of.
Interactivity
This is an interactive problem. Your solution will be tested against an interactive judge which reads the output of your solution and prints the input your solution receives. This interaction follows certain rules:
Your program must repeatedly instruct Tyrfingur through several rounds of interaction. In each round your program should perform one of the following operations.
-
print p to tell Tyrfingur to write down his current number,
-
print < to tell Tyrfingur to think of the smaller value his current value points to,
-
print > to tell Tyrfingur to think of the larger value his current value points to,
-
print ^ to tell Tyrfingur to think of the value that brought him to his current value,
-
print ! to tell Tyrfingur to put the paper in the envelope and seal it.
After each operation there might be an answer from the judge program which your program needs to read. In each round, after having printed the operation, your program should read:
-
one integer which is $1$ if the value is correct, or $0$ if your program made a mistake and should stop running immediately,
-
one integer which is $1$ if the operation succeeded and that value exists, or $0$ otherwise,
-
one integer which is $1$ if the operation succeeded and that value exists, or $0$ otherwise,
-
one integer which is $1$ if the operation succeeded and that value exists, or $0$ otherwise, which can only happen for the main value,
-
nothing and your program should stop running immediately.
These responses correspond to the operations above, given in the same order.
The number of values can be denoted by $n$, and it is guaranteed that $1 \leq n \leq 25\, 000$. You may try to switch between values at most $3n$ times.
Make sure to flush after each guess, for example using
-
print(..., flush=True) in Python,
-
cout << ... << endl; in C++,
-
System.out.flush(); in Java.
| Read | Sample Interaction 1 | Write |
|---|
<
1
<
0
p
1
>
1
<
0
p
1
>
0
^
1
^
1
p
1
>
1
<
0
p
1
>
0
^
1
^
0
!
