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

All Submissions
Best Solutions


Point Value: 5
Time Limit: 1.00s
Memory Limit: 16M
Added: Jan 18, 2009

Languages Allowed:

Comments (Search)

<
1
2
>

interactive problems fixed yet?

It's now 2017 and it is still not fixed yet.

How do you get the input from the grader? How do you get the response from the grader?

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

I thought it was all Keyboard/Screen I/O...

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;
}
}
}

Do you have the Phyton 3 template? I still don't really understand the flush system.

 
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

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 :(

Why is the language allowed box empty and why can't I submit in Python 3

They're probably changing the flush output judge or something.


Interactive problems are broken right now. You can see in the languages allowed in the right hand side that there are no languages allowed.

How do you read the judge feedback, I can flush it but I don't think that is imputed into my program

I think interactive problems are broken right now. I'll fix them eventually.

ok thanks.

Why is it that when I hand in my code and hand the same code in again, I get different marks?

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

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)?

The problem is perfectly clear; read it again.

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

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.)

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?

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).

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.

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.


Don't put readln, right after your flush(output).
Otherwise, the interactive program's output just gets dumped.

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?

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.

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.