## Guess the Number

An interactive problem

I'm thinking of a number between 1 and 2×109, inclusive.
Now it will be your job to try to find my number!

To guess a number, just print it out. See the wiki for instructions on flushing output in your language; you must do this after every guess you print.

I will output something back: "Higher" if your number is too low, or "Lower" if your number is too high.
I will output "OK" if you guessed correctly! Your program should stop at this point.

Your guessing algorithm must be optimal—you must take less than 32 guesses.

### Sample session

```You: 10
Me: Lower
You: 8
Me: Higher
You: 9
Me: OK```

Point Value: 5
Time Limit: 1.00s
Memory Limit: 16M

Languages Allowed:

<
1
2
>

• (9/0)
interactive problems fixed yet?

• (0/0)
It's now 2017 and it is still not fixed yet.

• (1/0)
How do you get the input from the grader? How do you get the response from the grader?

• (1/0)
There is no input. Read the grader's response just as you would normally read the input file of a non-interactive problem.

• (1/0)
I thought it was all Keyboard/Screen I/O...

• (1/0)
Template:
`` #include <iostream> #include <string> using namespace std;  int main() {     unsigned long guess = [initial guess];     string response;     while (1) {         cout << guess << endl; // endl automatically flushes in C++         cin >> response;         if (response == "Lower") {             guess = [lower guess];         } else if (response == "Higher") {             guess = [higher guess];         } else if (response == "OK") {             break;         }     } } ``

• (0/0)
Do you have the Phyton 3 template? I still don't really understand the flush system.

• (2/0)
`` import sys guess = #(initial guess) response = '' while (1):     print (guess)     sys.stdout.flush()     response = input()     if (response == "Lower"):         guess = #(lower guess)     elif (response == "Higher"):         guess = #(higher guess)     elif (response == "OK"):         break ``

• (1/0)
I can't see why putting guess and response outside the loop, but thanks man: I was about to give it a shot and even though I would have gone first for that road, you surely saved me some trial&error anxiety.

Too bad now it is not accepting Python 3 code :(

• (0/0)
Why is the language allowed box empty and why can't I submit in Python 3

• (1/0)
They're probably changing the flush output judge or something.

• (0/0)
Thanks!

• (0/0)
Interactive problems are broken right now. You can see in the languages allowed in the right hand side that there are no languages allowed.

• (1/0)
How do you read the judge feedback, I can flush it but I don't think that is imputed into my program

• (7/0)
I think interactive problems are broken right now. I'll fix them eventually.

• (1/0)
ok thanks.

• (0/0)
Why is it that when I hand in my code and hand the same code in again, I get different marks?

• (0/0)
The time limit (0.05 s) was too strict for Java, apparently, I doubled it.

• (1/1)
What is the number that I have to guess? Do you assign a number a variable at the beginning or do i need to use Random Generator? Is the number the same each time or different (Java)?

• (0/0)
The problem is perfectly clear; read it again.

• (0/0)
do you assign a number at the beginning? or is there something else that uses flush (i dont know i use java). THanks

• (0/0)
Yes, you output a number at the beginning as your first guess.

In addition: to flush in Java, use:
``System.out.flush();``

(Interestingly enough, neither of the two Java solutions do this, however.)

• (0/0)
I'm running my solution locally, and it works. But then i submit, it gives me invalid output. I don't think im understanding what I'm supposed to output, and what kind of input im supposed to expect.

Right now im doing:
10
Higher
15
Higher

Is this correct?

• (0/0)
Well first off, you seem to output 0 as your first guess.
Remember that it can be any number between 1 and 2 billion (and only between 1 and 2 billion).

• (0/0)
Even after I start from 1, I fail on the last 2 test cases. Is there anyway I can see what those test cases are?

Thanks.

• (0/0)
I'm not going to tell you what they are, but I can tell you what you output.

For test case #4, the TLE actually means that you've exceeded the allotted amount of guesses (you're taking 32 or more guesses).

For test case #5, your guess is -2147483648. (This is because when you cast it to an int32_t you get 2^32, which when converted to a signed number wraps around.)

The only thing I can tell you is you're approaching the problem incorrectly -- there's a more optimal (read: more correct) way to guess.

• (0/1)

• (0/0)
Otherwise, the interactive program's output just gets dumped.

• (0/0)
Can someone tell me what my problem is for the last test case?
I pretty sure its not the size of my numbers, but maybe its cause my codes somewhat inefficient?

• (0/0)
I skimmed your code and there isn't much wrong with it.

Instead of using b to control ceil/floor, try saving the previous guess.

• (2/0)
Yeah, a major problem associated with binary search is figuring out when to take the ceil and when to take the floor. Right now you seem to be alternating, which isn't great - try experimenting a bit. You may even have to use a different formula when you go up as opposed to when you go down, I won't tell you exactly what.