Interactive number guessing challenge. C++
This is an interactive task.
The jury program guesses an integer N (1 ≤ N ≤ 10^9), which your program will have to guess in no more than 100 attempts. You can make queries by inferring a number from a possible range of integers. In response to each request, the jury program will report the result of comparing the hidden number with the number in the request.
Interaction protocol After each request for an integer X your program will be informed in a new line of the result of comparing your number X with the hidden number N, which is expressed by the output of a single character with a line break:
"
">" : the hidden number is strictly greater than the number in the request (N > X);
"=" : the hidden number matches the number in the request (N = X), and your program should terminate immediately upon receiving such a response.
Your program should not produce more than 100 requests.
I think it is clear that here you need to use a binary search.
#include <iostream>
using namespace std;
int main()
{
long long l = 1, r = 10e9, mid = (l + r) / 2;
while (true)
{
char input;
mid = (l + r) / 2;
cout << mid << endl;
cin >> input;
if (input == '>')
l = mid + 1;
else if (input == '<')
r = mid - 1;
else if(input == '=')
return 0;
}
}
The program does not pass in time. So it's "stuck" somewhere? But where? And why? In theory, everything should work fine...
2 answers
Everything works, just don't take it 1010 as the maximum value, and 109 -
r = 1e9;
But even better - do not be petty, do not force to convert double to int - write as is:
r = 1'000'000'000;
Well, or if the compiler does not understand this (for ACMP, it does:)), then
r = 1000000000;
P.S. Probably, the testing system works with int, and your first sentence 5000000000 is perceived as 705032704, which leads to misunderstandings and looping at the number from - up to a billion...
Why so much extra? I would do this:
unsigned r = 1000000001, mid = r / 2, l = 1;
cout << mid;
char input{};
while ( cin >> input && input != '=')
{
if (input == '>')
l = mid;
else
r = mid;
mid = (l + r) / 2;
cout << mid;
}
return 0;
First, two billion is quite fit in unsigned int, and second, you output the answer and enter a character that can have three values, if not equal, then less or more.