Guess the Number#11355

Guess the Number

1 second

256 megabytes

Easy

This is an interactive problem. This means that during testing, a jury program (hereinafter referred to as the interactor) will run alongside your solution. Your program needs to "communicate" with it. For C++ and Python, a template is provided on how to communicate correctly.

The interactor has chosen a certain number from $1$ to $100$ . You need to guess this number. You can give numbers to the interactor, and it will respond whether the number it has chosen is greater or less than the one you provided.

For example, suppose the interactor has chosen the number $83$ . If you give it the number $30$ , it will say «greater». If the number $90$ , it will say «less». If $83$ , then «equal».

You need to figure out what this number is within $6$ questions.

You may find it useful to read about binary search.

Below you can find code in different languages that receives 6 points.

example.cpp example.java example.py

Interaction

You need to make queries in the following format:

«? x». Where $x$ ( $1 \leq x \leq 100$ 1 \leq x \leq 100) — the number you want to pass to the interactor. You can do this no more than $100$ times. You need to output this, and then output a newline character. After that, you must perform the flush operation. You need to read the response. If the number that the interactor has chosen is greater than yours, you will read the number $1$ . If less, then $- 1$ . If your number is the number that the interactor has chosen, you will read $0$ .

The flush operation in different languages should be performed as follows:

fflush(stdout) or cout.flush() in C++;
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;
for all other languages, you need to check the documentation yourself.

After you are confident about what number the interactor has chosen, you need to output «! x», a newline character, and perform the flush operation.

Examples

Example

1
-1
0

? 30
? 90
? 83
! 83

Example 1

Scoring

Let $q$ — the maximum number of questions among all tests.

If $q > 100$ q > 100, you will receive $0$ points.

Otherwise, you will receive $min (106 - q, 100)$ \min(106 - q, 100) points.