Problem H
Extraterrestrial Exploration
CC BY-SA 3.0 by Edwtie on Wikimedia Commons
After years of planning and construction, you finally succeeded in making your own spacecraft! Immediately hopping aboard, you take the spaceship on a maiden voyage to the Big Anthropomorphic Pig Constellation. After a couple of years, you reach the constellation and land on the nearest planet to take some pictures and hopefully score some souvenirs. While haggling with a local souvenir seller using the built-in translator of your spacecraft, you are suddenly notified that the craft is low on fuel! Your extensive use of the translator has drained more fuel than expected, and you cannot get back to Earth. Frantically, you look for a refuelling station. Luckily, a local points you to a shady store, strikingly similar to the petrol stations you know from home.
While the outside of the refuelling station may look similar to those on Earth, the inside is completely different. On a long shelf are a number of fuel canisters, with strange symbols on the side. From your research on rocket fuel, you deduce that these symbols probably denote the oxydilation level of the fuel in the canister. None of the rocket fuels burn on their own. Instead, combining two rocket fuels with oxydilation levels $o_x$ and $o_y$ yields a fuel with burn time $\sqrt{|o_x-o_y|}$. You can afford to buy three full canisters, and the burn time of rocket fuel is additive, so that combining rocket fuels with oxydilation levels $o_x$, $o_y$ and $o_z$ results in a total burn time of
\[ \sqrt{|o_x-o_y|} + \sqrt{|o_y-o_z|} + \sqrt{|o_z-o_x|}. \]You can only decode the symbols denoting the oxydilation levels with the translator of your spacecraft. Unfortunately, due to the low fuel levels of the spacecraft, you can only use your translator for $50$ items, before the fuel fully runs out. Luckily, you know that rocket fuel is always stored in non-decreasing order of oxydilation levels. Can you figure out which three canisters of rocket fuel to buy to maximize total burn time?
Interaction
This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:
The interactor first sends one line with an integer $n$ ($3\leq n\leq 2 \cdot 10^5$), the number of types of rocket fuel.
Then, your program should make at most $50$ queries to find the optimal three fuel canisters. Each query is made by printing one line of the form “? $i$” ($1\leq i\leq n$). The interactor will respond with one line with an integer $o_i$ ($|o_i| \leq 10^6$), the oxydilation value of the fuel in the $i$th canister.
When you have determined the optimal three distinct canisters $x$, $y$, and $z$ ($1 \leq x,y,z \leq n$, $x \neq y$, $x \neq z$, $y \neq z$), print one line of the form “! $x$ $y$ $z$”, after which the interaction will stop. Printing the answer does not count as a query.
If there are multiple valid solutions, you may output any one of them.
The interactor is not adaptive: the oxydilation levels of the fuel canisters are fixed up front, and do not depend on your queries.
Make sure you flush the buffer after each write.
A testing tool is provided to help you develop your solution.
Using more than $50$ queries will result in a wrong answer.
| Read | Sample Interaction 1 | Write |
|---|
4
? 1
1
? 3
3
? 4
3
! 1 2 3
| Read | Sample Interaction 2 | Write |
|---|
6
? 1
-5
? 6
5
? 2
-3
? 5
3
? 3
-1
? 4
1
! 4 6 1
