408281: GYM103076 D Lost Archive

This is an interactive problem.

Galdino downloaded his favorite game on his computer, but he can't remember in which folder he put it. In his computer there is a total of $$$N$$$ folders numbered from $$$1$$$ to $$$N$$$ and in only one of them he can find his favorite game. Fortunately, his friend Clippy promised to help.

Clippy offers Galdino the following game: you can choose two integers $$$L, R$$$ and I will tell you whether the game is in any of the folders in the interval $$$[L, R]$$$. However, you only have up to 25 tries and if you can't find your game until there, I will eat all of your files!

Feeling confident, Galdino decided to accept Clippy's risky game. Help him!

The first line of input will contain a single integer $$$N$$$ ($$$1 \le N \le 10^6$$$) indicating the number of folders in Galdino's computer.

When you feel that you found the right folder, print the string "! x", where $$$x$$$ is the index of the game's folder. After that, terminate your program.

To ask Clippy a question, print two integers $$$L, R$$$ ($$$1 \le L \le R \le N$$$) and flush the output. After flushing it, the answer for this query can be read from input.

After every query, it will be printed to input 0 if the game can't be found in any folder in $$$[L, R]$$$ or 1 otherwise.

To flush you can use:

• fflush(stdout) in C++;
• System.out.flush() in Java;
• stdout.flush() in Python;
• flush(output) in Pascal;
• see the documentation for other languages.

1

1

1 1

! 1

4

0

0

1

1 1

2 2

3 3

! 3