eolymp
bolt
Try our new interface for solving problems
Məsələlər

Интригующий выбор

Интригующий выбор

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

Вы — главный тренер шахматного клуба. В клубе 2n игроков, у каждого игрока есть некоторая сила, которую можно представить числом, и все эти числа различны. Силы игроков Вам не известны.

Вам следует выбрать n игроков, которые будут представлять Ваш клуб в предстоящем чемпионате. Естественно, Вы хотите выбрать n самых сильных игроков.

Для этого Вы можете организовывать матчи между игроками. В каждом матче Вы выбираете двух игроков, они играют несколько игр, и Вы узнаете, у кого из двоих больше сила. Вы можете дождаться исхода матча, прежде чем решить, кто будет участвовать в следующем.

Однако Вам нет необходимости знать, как эти n игроков соотносятся по силе между собой, поскольку это сделало бы сам чемпионат менее интригующим. Более формально, Вы должны достичь состояния, в котором существует ровно один способ выбрать n игроков с наивысшей силой, который соответствует результатам организованных Вами матчей. Однако должны быть как минимум два возможных порядка этих n игроков по силе, соответствующие результатам организованных Вами матчей.

Qarşılıqlı əlaqə

Ваша программа должна обработать несколько тестов. Сначала следует прочитать целое число t~(t \ge 1) — количество тестов. Затем следует обработать тесты один за другим.

В каждом тесте Ваша программа должна начинаться с чтения целого числа n~(3 \le n \le 100) — количества игроков, которых нужно выбрать из 2n игроков. Сумма квадратов значений n по всем тестам не превышает 10000.

Затем Ваша программа может организовывать матчи — ноль или более раз. Чтобы организовать матч, программа должна вывести описание матча в формате ? i j — вопросительный знак, за которым следуют два разных номера игроков, участвующих в матче. Игроки нумеруются от 1 до 2n включительно. Не забудьте очистить вывод после вывода описания матча. Затем программа должна прочитать результат матча — это будет либо символ "больше" (>), если первый игрок имеет более высокую силу, либо символ "меньше" (<), если у второго игрока сила выше.

Ваша программа может организовать не более 4 \cdot n^2 матчей. После завершения матчей программа должна вывести восклицательный знак (!) и перейти к следующему тесту или корректно завершить работу, если это был последний тест. Не забудьте очистить вывод после печати восклицательного знака.

Должен быть ровно один способ выбрать n игроков с наибольшей силой, соответствующий результатам организованных Вами матчей. Однако должно быть как минимум два возможных порядка этих n игроков по их силе, которые соответствуют результатам организованных матчей.

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

Nümunə

В первом тесте игроки отсортированы по силе в порядке убывания. Из матчей в примере мы можем сделать вывод, что игроки 1, 2 и 3 имеют наибольшую силу, но мы не знаем, насколько игрок 1 сравним с игроком 2.

Giriş verilənləri #1
2
3

>

<

>

<

>

>

3

<

<

<

>

>
Çıxış verilənləri #1

? 1 3

? 4 2

? 4 5

? 6 5

? 3 4

? 5 6

!

? 3 4

? 4 2

? 5 3

? 6 4

? 3 1

!
Mənbə 2019 ACM NEERC, Semifinals, December 1, Problem I