Задача №111479. Секрет осьминога Пауля
Как известно, футбольные матчи — это не просто спортивное состязание, но и возможность выиграть немного денег, удачно предсказав результаты матчей. В преддверии чемпионата мира по футболу Вася решил попытать счастья и сделать ставку на финальную игру, но тут же столкнулся с проблемой: любая команда, участвующая в чемпионате, по его расчетам могла бы выиграть в финале, а значит шансов угадать команду-победителя крайне мало.
Чтобы облегчить себе задачу, Вася решил обратиться за помощью к прославленному игроку на тотализаторе осьминогу Паулю. Дело в том, что Вася знает, как осьминог делает свои безошибочные предсказания. Перед началом соревнований Пауль каким-то образом делит команды на три группы по силе: самые сильные команды, средние и самые слабые. Чтобы спрогнозировать результат игры, Пауль смотрит на силу команд, принимающих участие в матче. Если команды находятся в разных по силе группах, он выбирает команду, из более сильной с его точки зрения группы, иначе осьминог просто не знает, какая команда победит.
Для того, чтобы сделать точный прогноз на финальный матч, Вася очень хочет узнать, как же именно Пауль разбивает команды на группы по силе. Немного подумав, мальчик понял, что разбиение возможно восстановить по прогнозам осьминога. Для этого достаточно несколько раз задать ему вопрос вида: "Сильнее или слабее команда a чем команда b". К сожалению, Вася может задать осьминогу ограниченное число вопросов (не более 106), иначе Пауль догадается, что мальчик хочет раскрыть его секрет.
Если осьминог понимает, что из его предыдущих ответов ясно следует ответ на текущий вопрос, то он впадает в ярость и крушит всё подряд.
Это — интерактивная задача. На стандартный вход участнику подается единственное число N(1 ≤ N ≤ 100000) — количество команд-участников в чемпионате. Затем участник начинает "общение" с осьминогом Паулем: необходимо последовательно подавать на стандартный поток вывода запросы вида a b, где a и b - номера команд, чье соотношение сил хочет узнать Вася (числа a и b должны быть разделены ровно одним пробелом, после числа b должен быть поставлен перенос строки). В ответ на запрос на стандартный поток ввода подается одно число — либо 1, если команда a сильнее команды b, либо -1, если команда a слабее, либо 0, если осьминог не знает какая команда победит. Участник должен считать данное число и вывести следующий запрос. Если программа делает запрос, ответ на который следует из предыдущих, то она завершается и ответ считается неверным.
Когда программа участника восстановила исходное разбиение команд по группам, то вместо запроса нужно вывести на стандартный поток вывода одно число 0, затем само разбиение в 4-х строках, где: в первой строке должно быть записано одно число - количество команд в самой сильной группе, во второй - команды, составляющие собой сильнейшую группу в произвольном порядке, в третьей - количество команд во второй по силе группе, в четвертой - команды, составляющие собой вторую по силе группу в произвольном порядке. Все числа должны быть отделены друг от друга ровно одним пробелом. В конце файла должен стоять перенос строки. После вывода распределения команд программа должно завершаться.
При выводе запросов следует пользоваться следующими фрагментами:
{язык Pascal/Delphi}
writeln(a, ' ', b); // вывод запроса.
flush(output);
//язык C
printf("%d %d\n", a, b);
fflush(stdout);
//язык C++
cout ≤≤ a ≤≤ " " ≤≤ b ≤≤ endl ≤≤ flush;
3
-1
-1
1 2
2 3
Пример общения программы участника с осьминогом Паулем:
3 число команд, поступает на вход решению
1 2 первый запрос
-1 ответ
2 3 второй запрос
-1 ответ
0 решение говорит о том что распределение команд установлено
1 число команд в самой сильной группе
3 список команд в самой сильной группе
1 число команд в средней группе
2 список команд средней группы