Интригующий выбор
Интригующий выбор
Это интерактивная задача.
Вы — главный тренер шахматного клуба. В клубе 2n игроков, у каждого игрока есть некоторая сила, которую можно представить числом, и все эти числа различны. Силы игроков Вам не известны.
Вам следует выбрать n игроков, которые будут представлять Ваш клуб в предстоящем чемпионате. Естественно, Вы хотите выбрать n самых сильных игроков.
Для этого Вы можете организовывать матчи между игроками. В каждом матче Вы выбираете двух игроков, они играют несколько игр, и Вы узнаете, у кого из двоих больше сила. Вы можете дождаться исхода матча, прежде чем решить, кто будет участвовать в следующем.
Однако Вам нет необходимости знать, как эти n игроков соотносятся по силе между собой, поскольку это сделало бы сам чемпионат менее интригующим. Более формально, Вы должны достичь состояния, в котором существует ровно один способ выбрать n игроков с наивысшей силой, который соответствует результатам организованных Вами матчей. Однако должны быть как минимум два возможных порядка этих n игроков по силе, соответствующие результатам организованных Вами матчей.
Протокол взаимодействия
Ваша программа должна обработать несколько тестов. Сначала следует прочитать целое число t~(t \ge 1) — количество тестов. Затем следует обработать тесты один за другим.
В каждом тесте Ваша программа должна начинаться с чтения целого числа n~(3 \le n \le 100) — количества игроков, которых нужно выбрать из 2n игроков. Сумма квадратов значений n по всем тестам не превышает 10000.
Затем Ваша программа может организовывать матчи — ноль или более раз. Чтобы организовать матч, программа должна вывести описание матча в формате ? i j — вопросительный знак, за которым следуют два разных номера игроков, участвующих в матче. Игроки нумеруются от 1 до 2n включительно. Не забудьте очистить вывод после вывода описания матча. Затем программа должна прочитать результат матча — это будет либо символ "больше" (>), если первый игрок имеет более высокую силу, либо символ "меньше" (<), если у второго игрока сила выше.
Ваша программа может организовать не более 4 \cdot n^2 матчей. После завершения матчей программа должна вывести восклицательный знак (!) и перейти к следующему тесту или корректно завершить работу, если это был последний тест. Не забудьте очистить вывод после печати восклицательного знака.
Должен быть ровно один способ выбрать n игроков с наибольшей силой, соответствующий результатам организованных Вами матчей. Однако должно быть как минимум два возможных порядка этих n игроков по их силе, которые соответствуют результатам организованных матчей.
Судейская программа выбирает несколько разных чисел в качестве сил всех игроков, прежде чем Ваша программа начнет организовывать матчи, и использовать их для ответа на запросы.
Пример
В первом тесте игроки отсортированы по силе в порядке убывания. Из матчей в примере мы можем сделать вывод, что игроки 1, 2 и 3 имеют наибольшую силу, но мы не знаем, насколько игрок 1 сравним с игроком 2.
2 3 > < > < > > 3 < < < > >
? 1 3 ? 4 2 ? 4 5 ? 6 5 ? 3 4 ? 5 6 ! ? 3 4 ? 4 2 ? 5 3 ? 6 4 ? 3 1 !