Problem C
Diabolic Doofenshmirtz
Interaction
Your submission can print “? t” where $t$ ($0\leq t<10^{18}$) is the point in time when you want to use the Measurinator. The time $t=0$ marks the point in time where Perry starts practicing i.e. where he starts his first lap at the start and finish line. The Measurinator responds with a single integer $x$ which is the current position of Perry in his current lap. Note that the Measurinator will not respond with the number of meters Perry has already crawled in total! Thus, whenever Perry reaches the start and finish line, the Measurinator will respond with $0$. Further note that you recently lost your Timetravellinator and therefore, the values of $t$ must be strictly increasing.
If you determined the length $x$ of one lap, print “! x”. After this, your program should immediately terminate.
All interactions must be ended by a newline. Further note that you additionally need to flush the standard output to ensure that the query is sent. For example, you can use:
-
std::cout << std::flush in C++
-
fflush(stdout) in C
-
System.out.flush() in Java
-
sys.stdout.flush() in Python
Your submission is considered correct if you followed these rules, found the correct length of one lap, and used no more than $42$ queries. Note that giving the answer is also counted as a query.
It is guaranteed that one lap has integer length, is at least one meter long, and at most $10^{12}$ meters long.
A testing tool is provided to help you develop your
solution. It can be downloaded from the DOMjudge problems
overview page.
| Read | Sample Interaction 1 | Write |
|---|
? 1
1
? 2
2
? 3
3
? 4
4
? 100
16
! 42
| Read | Sample Interaction 2 | Write |
|---|
? 10
10
? 20
20
? 30
30
? 40
40
? 10000
641
! 1337
