Интерактивные задачи

В обычной задаче вы читаете входные данные и печатаете ответ. В интерактивной — ведёте диалог: спрашиваете, судья отвечает, вы спрашиваете дальше.

Классическая постановка — «угадай число». Судья загадал число от 1 до $10^9$, вы называете кандидата, вам говорят «больше», «меньше» или «угадал». Разрешено тридцать вопросов. Тридцать — это $\log_2 10^9$, и подсказка тут прозрачная: нужен бинарный поиск.

Интерактивные задачи почти всегда про поиск. Ограничение на число запросов прямо называет нужную асимптотику: $30$ вопросов — логарифм, $2n$ — два прохода, $n \log n$ — сортировка плюс поиск.

Сброс буфера — главная причина провалов

cout не отправляет данные сразу. Он копит их в буфере и выводит пачками по несколько килобайт — так быстрее. В обычной задаче это незаметно. В интерактивной — фатально: вы задали вопрос, он остался в буфере, судья его не получил, вы ждёте ответа, судья ждёт вопроса. Взаимная блокировка, вердикт по таймауту.

Поэтому после каждого вопроса буфер нужно сбрасывать:

cout << "? " << mid << endl;      // endl = '\n' + flush
// или явно:
cout << "? " << mid << "\n";
cout.flush();

Это единственное место, где endl действительно нужен. В обычных задачах он только замедляет вывод, и там пишут '\n'.

В других языках:

язык	сброс
C++	cout << endl; или cout.flush();
Python	print(x, flush=True)
Java	System.out.flush();
C	fflush(stdout);

И отдельно: в интерактивных задачах нельзя писать ios::sync_with_stdio(false) вместе с cin.tie(nullptr). Отвязка cin от cout как раз убирает автоматический сброс перед чтением — то есть ровно ту страховку, которая могла бы вас спасти.

Оберните запрос в функцию

Формат вопроса обычно нетривиален: знак вопроса, пробелы, конкретный порядок аргументов. Если запрос делается из пяти мест в коде, вы пять раз рискуете ошибиться в формате.

string ask(long long value) {
    cout << "? " << value << endl;
    string reply;
    cin >> reply;
    if (reply == "MISTAKE") exit(0);   // судья сообщил об ошибке
    return reply;
}

void answer(long long value) {
    cout << "! " << value << endl;
    exit(0);
}

Дальше основной код читается как обычный бинарный поиск:

long long lo = 1, hi = 1000000000;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    string reply = ask(mid);
    if (reply == "<") hi = mid - 1;
    else if (reply == ">") lo = mid + 1;
    else answer(mid);
}
answer(lo);

Вся возня с форматом заперта в двух функциях, а логика осталась чистой.

Локальное жюри

Отлаживать интерактивную задачу, вводя ответы руками, невозможно: тридцать шагов по одному числу — и вы устали раньше, чем нашли ошибку.

Решение — подменить ask на функцию, которая сама играет за судью:

#ifdef LOCAL
long long secret = 524287;
int queries = 0;
string ask(long long value) {
    if (++queries > 30) { cerr << "превышен лимит запросов\n"; exit(1); }
    if (value == secret) return "=";
    return value < secret ? ">" : "<";
}
void answer(long long value) {
    if (value != secret) { cerr << "неверный ответ: " << value << "\n"; exit(1); }
    cerr << "верно за " << queries << " запросов\n";
    exit(0);
}
#endif

Компилируется это флагом -DLOCAL, и на сервере блок просто не попадает в сборку.

Дальше — обычный стресс: перебираем secret по всем значениям от 1 до 1000 и проверяем, что решение угадывает каждое и укладывается в лимит запросов. Ошибка на границе, которую вручную ловили бы час, находится за секунду.

Правила протокола

Формат соблюдается буквально. Если в условии написано «выведите ? x», то именно так, с пробелом. Лишний символ — и судья вас не поймёт.

Команда «завершиться» выполняется немедленно. Многие задачи описывают: «если вы получили $-1$, немедленно завершите программу». Не завершились — получите не «неверный ответ», а что угодно: превышение времени, ошибку исполнения, превышение памяти. Разбираться в таком вердикте бесполезно, потому что он не про вашу ошибку.

Число запросов считается строго. Лишний вопрос — сразу отказ. Если алгоритм делает $\lceil \log_2 n \rceil$ запросов, а разрешено ровно столько же, проверьте на границах: при $n$, равном степени двойки, легко получить на один запрос больше.

Не выводите отладку в cout. Судья прочитает её как ваш запрос. Всё лишнее — в cerr.

Адаптивный судья

Отдельный подвох: судья не обязан загадывать число заранее. Он может выбирать ответ так, чтобы вам было хуже всего, — лишь бы не противоречить уже сказанному.

Против такого судьи «повезло угадать» не работает: если ваш алгоритм в среднем укладывается в лимит, но в худшем случае нет, он не пройдёт. Нужна оценка сверху для худшего случая, а не для среднего.

Признак адаптивного судьи в условии — фразы вроде «жюри может менять загаданное значение, если это не противоречит предыдущим ответам». Локальное жюри для такой задачи тоже стоит написать вредным: пусть отвечает так, чтобы оставлять себе больше вариантов.