Codeforces Round 427 (Div. 2) |
---|
Закончено |
Обратите внимание: эта задача интерактивная.
Пингвин Ксорий недавно придумал новую игру. У него есть n сосулек, занумерованных целыми числами от 1 до n. Каждая сосулька имеет температуру — целое число от 1 до 109. Ровно две из этих сосулек особые: их температура равна y, в то время как температура всех остальных сосулек равна x ≠ y. Вам нужно найти две особые сосульки. Вы можете не более 19 раз выбрать некоторое непустое подмножество сосулек и спросить у пингвина, чему равно побитовое исключающее ИЛИ (XOR) температур сосулек из этого подмножества.
Вам необходимо найти особые сосульки.
Первая строка содержит три целых числа n, x, y (2 ≤ n ≤ 1000, 1 ≤ x, y ≤ 109, x ≠ y) — количество сосулек, температура обычных сосулек и температура особых сосулек.
Чтобы сообщить пингвину свой ответ, выведите символ «!» (без кавычек), затем два целых числа p1, p2 (p1 < p2) — номера особых сосулек в порядке возрастания. Обратите внимание, что «!» и p1 должны быть разделены пробелом; номера также должны быть разделены пробелом. После того, как вы сообщили ответ, ваша программа должна немедленно завершиться.
Чтобы задать вопрос, выведите символ «?» (без кавычек), число c (1 ≤ c ≤ n), а затем c различных чисел p1, p2, ..., pc (1 ≤ pi ≤ n) — номера сосулек, про которые вы хотите узнать информацию. Обратите внимание, что «?» и c должны быть разделены пробелом; номера также должны быть разделены пробелами.
После того, как вы задали вопрос, необходимо считать одно число — ответ на вопрос.
Обратите внимание, что вы можете задать не более 19 вопросов. В случае, если вы зададите больше 19 вопросов или зададите хотя бы один некорректный вопрос, ваше решение получит вердикт «Неправильный ответ».
Если в какой-то момент ваша программа считывает - 1 как ответ, она должна немедленно завершиться (например, вызовом exit(0)). Вы получите вердикт «Неправильный ответ», и это будет означать, что вы задали больше 19 вопросов или задали некорректный вопрос. Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.
Выше решение получит вердикт «Решение зависло», если вы не будете ничего выводить или забудете сделать операцию flush после вывода вопроса или ответа.
Чтобы выполнить операцию flush, можете использовать (сразу после вывода чисел и перевода строки):
Взломы
Используйте следующий формат для взломов:
n x y p1 p2
Здесь 1 ≤ p1 < p2 ≤ n — номера особых сосулек.
Взламываемая программа не будет иметь доступа к этим данным.
4 2 1
2
1
1
? 3 1 2 3
? 1 1
? 1 3
! 1 3
Для первого вопроса ответ равен .
Для второго и третьего вопросов ответ равен 1, следовательно, особые сосульки имеют номера 1 и 3.
Вы можете узнать больше про побитовый XOR здесь: https://ru.wikipedia.org/wiki/Битовые_операции.
Название |
---|