Это сложная версия задачи. В этой версии вы должны использовать минимально возможное количество запросов. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Это интерактивная задача.
На сборах сборной Мексики к IOI существует традиция играть в игру «Ассасин», которая похожа на «Among Us» или «Мафию».
Сегодня \(n\) игроков, пронумерованных от \(1\) до \(n\), будут играть в «Ассасин» со следующими тремя ролями:
- Рыцарь: Рыцарь — это тот, кто всегда говорит правду.
- Лжец: Лжец — это тот, кто всегда лжет.
- Предатель: Предатель — это тот, кого все считают Рыцарем, а на самом деле он Лжец.
Каждому игроку будет назначена своя роль в игре. В игре будет ровно один Предатель, но может быть любое (возможно нулевое) количество Рыцарей и Лжецов.
Вы были ведущим игры, но случайно забыли роли всех игроков, поэтому вам нужно определить игрока, который является Предателем.
Чтобы определить Предателя, вы зададите несколько вопросов. В каждом вопросе вы выбираете двух игроков \(i\) и \(j\) (\(1 \leq i, j \leq n\); \(i \neq j\)) и спрашиваете, считает ли игрок \(i\), что игрок \(j\) — Рыцарь. Результаты этого вопроса приведены в таблице ниже.
| Рыцарь | Лжец | Предатель |
| Рыцарь | Да | Нет | Да |
| Лжец | Нет | Да | Нет |
| Предатель | Нет | Да | — |
Значение ячейки в строке \(a\) и столбце \(b\) — это ответ на вопрос, когда \(i\) имеет роль \(a\), а \(j\) — роль \(b\). Например, «Да» в правой верхней ячейке принадлежит строке «Рыцарь» и столбцу «Предатель», поэтому это ответ на вопрос, когда \(i\) — Рыцарь, а \(j\) — Предатель. Найти Предателя за минимально возможное количество запросов. Иными словами, пусть \(f(n)\) — минимальное число, такое, что для \(n\) игроков существует стратегия, позволяющая определить Предателя, используя не более \(f(n)\) вопросов. Тогда для определения Предателя нужно использовать не более \(f(n)\) вопросов.
Заметьте, что итерактор адаптивен: роли игроков не фиксированы изначально и могут меняться в зависимости от ваших вопросов. Однако гарантируется, что существует такое распределение ролей, которое соответствует всем ранее заданным вопросам в ограничениях этой задачи.
Протокол взаимодействия
Чтобы задать вопрос, выведите строку в следующем формате:
- «? i j» (\(1 \leq i,j \leq n\); \(i \neq j\)) — спросить игрока \(i\), считает ли он игрока \(j\) Рыцарем.
Жюри выдаст «1», если игрок \(i\) считает игрока \(j\) Рыцарем, и «0» в противном случае.
Когда вы определите, какой игрок является Предателем, выведите строку в следующем формате:
- «! i» (\(1 \leq i \leq n\)) — Предателем является игрок \(i\).
Обратите внимание, что ответы не учитываются в ограничении в \(f(n)\) вопросов.
Если вы сделали некорректный вывод, использовали более \(f(n)\) вопросов или неверно определили Предателя, жюри ответит «-1», и вы получите вердикт Неправильный ответ. Получив «-1», ваша программа должна немедленно завершиться. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит чтение из закрытого потока.
После каждого вывода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- sys.stdout.flush() в Python;
- std::io::stdout().flush() в Rust;
- смотрите документацию для других языков.
Формат взломов
Для взломов используйте следующий формат.
Первая строка должна содержать одно целое число \(t\) — количество наборов входных данных.
Первая строка каждого набора входных данных должна содержать целое число \(n\), за которым следует строка «manual».
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(-1 \le a_i \le 1\)) — роли каждого игрока. \(1\) обозначает Рыцаря, \(0\) — Лжеца, а \(-1\) — Предателя. Предатель должен быть ровно один, то есть должен быть ровно один индекс \(i\) такой, что \(a_i=-1\).
В качестве примера приводим взлом, аналогичный примеру из условия:
2
7 manual
0 1 0 -1 0 1 0
4 manual
0 1 -1 0
Примечание
Обратите внимание, что примеры не представляют собой оптимальную стратегию задавания вопросов и приведены только для демонстрации формата взаимодействия. В частности, мы не можем определить, кто из игроков является Предателем, по вопросам, заданным в примерах.
В первом наборе входных данных игроки с индексами \(2\) и \(6\) — Рыцари, игроки с индексами \(1\), \(3\), \(5\) и \(7\) — Лжецы, а Предатель имеет индекс \(4\). Ниже приводится объяснение заданных вопросов:
- В первом вопросе игрок \(i\) является Лжецом, и игрок \(j\) также Лжец. Ответ — «да», так как Лжецы всегда лгут.
- Во втором вопросе игрок \(i\) — Лжец, а игрок \(j\) — Рыцарь. Ответ — «нет», так как Лжецы всегда лгут.
- В третьем вопросе игрок \(i\) — Рыцарь, а игрок \(j\) — Лжец. Ответ — «нет», так как Рыцари всегда говорят правду.
- В четвертом вопросе игрок \(i\) — Рыцарь, и игрок \(j\) также Рыцарь. Ответ — «да», так как Рыцари всегда говорят правду.
- В пятом вопросе игрок \(i\) — Предатель, а игрок \(j\) — Лжец. Ответ — «да», так как Предатель всегда лжет.
- В шестом вопросе игрок \(i\) — Предатель, а игрок \(j\) — Рыцарь. Ответ — «нет», так как Предатель всегда лжет.
- В седьмом вопросе игрок \(i\) — Лжец, а игрок \(j\) — Предатель. Ответ — «нет», так как Лжецы всегда лгут, и Лжецы думают, что Предатель является Рыцарем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
7
1
0
0
1
1
0
0
4
0
1
1
1
|
? 1 3
? 7 6
? 2 5
? 6 2
? 4 5
? 4 6
? 1 4
! 4
? 1 2
? 2 3
? 3 4
? 4 1
! 3
|