Josh is an egg inspector! One of his clients has varieties of eggs labelled from to , living in a house with floors labelled from to , bottom to top. The -th variety of egg will shatter if and only if it is dropped from the floor or higher. It is guaranteed that is a permutation of the integers from to . Josh's job is to determine this hidden permutation.
Josh has unlimited eggs of each variety, and can test the eggs by dropping them from different floors in the house. Initially, he is in an elevator on floor . In one move he can do one of the following:
- Drop an egg of a chosen variety from the current floor, and see whether it shatters or not.
- Move the elevator up or down by floor.
Additionally, the elevator is old, so it should not change directions frequently. Every time the direction of the elevator's movement is different to its previous movement's direction, an extra penalty of moves will be incurred.
Can you help Josh determine the permutation using as few moves as possible? You may drop at most eggs.
is a permutation of the integers , generated uniformly at random.
Let be the maximum number of moves made by your program in any test case. Your program will receive the following score:
If your program fails to correctly guess the permutation in any test case, then you will receive points.
This is an interactive problem. Note that the interactor is not adaptive.
At first, you should read in a single integer on a single line, representing the value of .
Then, you will have the opportunity to make up to queries. To make a query, output a line in the form
? e f. This corresponds to moving the elevator to floor , and dropping an egg of the -th variety. This will incur moves, where is the previous location of the elevator. Furthermore, if and the direction of the elevator's movement is different to its last movement's direction, additional moves will be incurred. Then, you should read in a single integer on a single line. This integer will be if the chosen egg shatters, and otherwise.
Finally, once you have made all of your queries, you should output a line in the form
! p_1 p_2 ... p_N, where is the permutation which you believe is the hidden permutation.
If at any point you format your queries incorrectly, or ask more than queries, the interactor will respond with on a single line. After receiving this feedback, you should terminate your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict.
If you successfully guess the correct sequence, then you will receive an Accepted verdict for that test case. Your final score for the problem will be determined through the aforementioned scoring mechanism. You will be told the number of queries that you used.
Please note that you may need to flush
stdout after each operation, or interaction may halt. In C++, this can be done with
cout << flush (depending on whether you use
cout). In Java, this can be done with
System.out.flush(). In Python, you can use
>>> denotes your output. Do not print this out.
3 >>> ? 2 1 1 >>> ? 1 3 1 >>> ? 3 2 0 >> ! 2 1 3
The hidden permutation is .
For the first query, the elevator stays at floor , and an egg of the -nd variety is dropped, shattering. This query incurs move, since the elevator does not move, and a single egg is dropped.
For the second query, the elevator moves up from floor to , and an egg of the -st variety is dropped, shattering. This query incurs moves, since the elevator moves twice, and a single egg is dropped. Since this is the first movement of the elevator, no additional moves for changing direction are incurred.
For the third query, the elevator moves down from floor to , and an egg of the -rd variety is dropped, without shattering. This query incurs moves, since the elevator moves once, and a single egg is dropped. Since the elevator has changed direction from up to down, additional moves are incurred.
In total, moves have been made, and the permutation has been correctly guessed, so the score for this test case would be .