Это простая версия задачи. В этой версии вы можете задать не более \(n+69\) вопросов. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Это интерактивная задача.
На сборах сборной Мексики к 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\) — Предатель. Найдите Предателя не более чем за \(n + 69\) вопросов.
Заметьте, что итерактор адаптивен: роли игроков не фиксированы изначально и могут меняться в зависимости от ваших вопросов. Однако гарантируется, что существует такое распределение ролей, которое соответствует всем ранее заданным вопросам в ограничениях этой задачи.
Протокол взаимодействия
Чтобы задать вопрос, выведите строку в следующем формате:
- «? i j» (\(1 \leq i,j \leq n\); \(i \neq j\)) — спросить игрока \(i\), считает ли он игрока \(j\) Рыцарем.
Жюри выдаст «1», если игрок \(i\) считает игрока \(j\) Рыцарем, и «0» в противном случае.
Когда вы определите, какой игрок является Предателем, выведите строку в следующем формате:
- «! i» (\(1 \leq i \leq n\)) — Предателем является игрок \(i\).
Обратите внимание, что ответы не учитываются в ограничении в \(n+69\) вопросов.
Если вы сделали некорректный вывод, использовали более \(n+69\) вопросов или неверно определили Предателя, жюри ответит «-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\) — Предатель. Ответ — «нет», так как Лжецы всегда лгут, и Лжецы думают, что Предатель является Рыцарем.
- В восьмом вопросе игрок \(i\) — Рыцарь, а игрок \(j\) — Предатель. Ответ — «да», так как Рыцари всегда говорят правду, и Рыцари думают, что Предатель является Рыцарем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
7
1
0
0
1
1
0
0
1
4
0
1
1
1
|
? 1 3
? 7 6
? 2 5
? 6 2
? 4 5
? 4 6
? 1 4
? 2 4
! 4
? 1 2
? 2 3
? 3 4
? 4 1
! 3
|