Интерактивные задачи: руководство для участника

Автор MikeMirzayanov, 3 года назад, , 

Иногда на соревнованиях по программированию (в том числе и на Codeforces) вы можете встретить интерактивные задачи.

При тестировании вашего решения по интерактивной задаче тот ввод, что будет подаваться в ваше решение (то есть те данные, что ваше решение читает) не являются заранее заготовленными, а строятся непосредственно в процессе тестирования вашей программы. Для этого жюри пишет специальную программу интерактор, вывод которой отправляется в ваше решение, а вывод вашего решения отправляется в интерактор. Иными словами, ваше решение и интерактор работают в паре и как ваше решение, так и интерактор могут принимать решение о том, что в данный момент вывести на основании "истории общения".

При написании решения для интерактивной задачи важно помнить, что если вы что-то вывели, то без специального указания в программе эти данные могут на самом деле попасть во внутренний буфер и не быть выведенными немедленно. Это может привести к ситуации, что интерактор "не увидел" ваш вывод. Для того, чтобы быть уверенным, что порция данных была передана в интерактор надо использовать операцию flush, которая наверняка есть в стандартной библиотеке вашего языка. Например, при программировании на C++ надо использовать fflush(stdout) или cout << flush (в зависимости от того вы выводите с помощью scanf/printf или cout). В Java надо использовать метод flush у потока вывода, например, System.out.flush(). В языке Python можно использовать stdout.flush(). В языке Pascal можно применять flush(output).

Рассмотрим следующую интерактивную задачу. Её вы можете попробовать решить самостоятельно по ссылке http://codeforces.com/gym/101021/problem/A

Есть несколько особенностей характерных для интерактивных задач:

• Ввод-вывод в интерактивных задачах работает значительно медленнее чем для обычных задач — старайтесь использовать scanf/printf вместо cin/cout в С++, BufferedReader/PrintWriter в Java и так далее.
• Ручное тестирование решений для интерактивных задач обычно значительно сложнее, так как участнику самому нужно исполнять роль интерактора во время тестирования.
• Вкладка "Запуск" ничего не знает об интеракторе для задачи, поэтому ее не получится использовать для полноценного тестирования решения.
• На раундах Codeforces иногда будут использоваться интерактивные задачи, в этом случае в условии задачи будет описан формат тестов для взломов.
• Вывод endl в cout в C++ автоматически делает операцию flush.

Задача

Условие

Напишите программу, которой предстоит в интерактивном режиме угадать число x, загаданное системой. Про загаданное число известно, что оно целое и лежит в границах от 1 до 10⁶ включительно.

Вы можете делать запросы к тестирующей системе, каждый запрос — это вывод одного целого числа от 1 до 10⁶. Есть два варианта ответа тестирующей системы на запрос:

• строка <, если загаданное число меньше числа из запроса;
• строка >=, если загаданное число больше либо равно числу из запроса.

В случае, если ваша программа считает, что определила загаданное число, выведите строку вида ! x, где x — это ответ, и завершите работу своей программы.

Вашей программе разрешается сделать не более 25 запросов (не считая вывода ответа).

Входные данные

Для чтения ответов на запросы программа должна использовать стандартный ввод.

Входные данные будут содержать ответы на запросы, то есть строки вида < и >=. i-я из этих строк является ответом системы на i-й запрос. После того, как ваша программа угадала число, выведите ! x (без кавычек), где x — это ответ, и завершите работу своей программы.

Тестирующая система даст вашей программе прочитать ответ на запрос из входных данных только после того, как ваша программа вывела соответствующий запрос системе и выполнила операцию flush.

Выходные данные

Для осуществления запросов программа должна использовать стандартный вывод.

Ваша программа должна выводить запросы — целые числа x_i (1 ≤ x_i ≤ 10⁶) по одному в строке. После вывода каждой строки программа должна выполнить операцию flush.

Каждое из значений x_i обозначает очередной запрос к системе. Ответ на запрос программа сможет прочесть из стандартного ввода. В случае, если ваша программа угадала число, выведите строку вида ! x (без кавычек), где x — ответ, и завершите работу программы.

Решение

Конечно, эту задачу следует решать бинарным поиском по ответу. Вот пример решения на C++:

#include <cstdio>
#include <cstring>

using namespace std;

int main() {
 int l = 1, r = 1000000;
 while (l != r) {
 int mid = (l + r + 1) / 2;
 printf("%d\n", mid);
 fflush(stdout);

 char response[3];
 scanf("%s", response);
 if (strcmp(response, "<") == 0)
 r = mid - 1;
 else
 l = mid;
 }

 printf("! %d\n", l);
 fflush(stdout);
}

Желаем полных решений. Еще раз напоминаем, что ознакомиться с интерактивной задачей можно по ссылке http://codeforces.com/gym/101021/problem/A

Источник статьи http://codeforces.com/blog/entry/45307?locale=ru