Интерактивная задача на угадывание числа. C++

Question

Это интерактивная задача.

Программа жюри загадывает целое число N (1 ≤ N ≤ 10^9), которое ваша программа должна будет отгадать не более чем за 100 попыток. Вы можете делать запросы путем вывода числа из возможного диапазона целых чисел. В ответ на каждый запрос программа жюри будет сообщать результат сравнения загаданного числа с числом в запросе.

Протокол взаимодействия После каждого запроса целого числа X вашей программе будет сообщено в новой строке результат сравнения вашего числа X с загаданным числом N, что выражается выводом одного символа с переносом строки:

"<" : загаданное число строго меньше числа в запросе (N < X);

">" : загаданное число строго больше числа в запросе (N > X);

"=" : загаданное число совпадает с числом в запросе (N = X), при получении такого ответа ваша программа должна немедленно завершиться.

Ваша программа должна произвести не больше 100 запросов.

Я думаю понятно, что тут нужно использовать бинарный поиск.

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

Программа не проходит по времени. Значит где-то "застревает"? Но где? И почему? По идее все должно работать нормально...

Answer 1

Зачем столько лишнего? Я бы сделал так:

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;

Во первых два миллиарда вполне вмещается в unsigned int, во вторых, вы выводите ответ и вводите символ, который может иметь три значения, если не равно, значит меньше или больше.

Answer 2

Все работает, просто берите не 10¹⁰ в качестве максимального значения, а 10⁹ -

r = 1e9;

Но еще лучше - не мелочитесь, не заставляйте преобразовывать double в int - пишите как есть:

r = 1'000'000'000;

Ну, или если компилятор этого не понимает (у ACMP - понимает :)), то

r = 1000000000;

P.S. Вероятно, тестирующая система работает с int, и ваше первое предложение 5000000000 воспринимает как 705032704, что и приводит к непоняткам и зацикливанию при числе от указанного до миллиарда...

БЛОГ НА HUSL

Интерактивная задача на угадывание числа. C++

Ответы (2 шт):