Это интерактивная задача!
Мистер 1048576 — один из тех преподавателей, который ненавидит тратить время на ведение посещаемости. Вместо того чтобы вести посещаемость традиционным способом, он решил попробовать что-то новое сегодня.
В его классе \(n\) студентов с номерами от \(1\) до \(n\). Он точно знает, что сегодня отсутствует ровно \(1\) студент. Чтобы определить, кто отсутствует, он может задать некоторые запросы классу. В каждом запросе он может указать два целых числа \(l\) и \(r\) (\(1\leq l\leq r\leq n\)), и все студенты, чьи номера от \(l\) до \(r\) (включительно), поднимут руки. Затем он подсчитывает их, чтобы определить, лежит ли номер отсутствующего студента между этими значениями.
Все было хорошо, пока его ассистент не заметил что-то странное — студенты нечестные! Некоторые студенты, чьи номера находятся в указанном диапазоне, могут не поднимать руки, в то время как другие студенты, чьи номера не находятся в указанном диапазоне, могут поднять руки и дать прокси-посещаемость за кого-то другого. Но они не хотят вызывать подозрений. Таким образом, возможны только следующие \(4\) случая для конкретного запроса \((l,r)\) —
- Истинно положительный: присутствуют \(r-l+1\) студент и \(r-l+1\) студент подняли руки.
- Истинно отрицательный: присутствуют \(r-l\) студентов и \(r-l\) студентов подняли руки.
- Ложно положительный: присутствуют \(r-l\) студентов, но \(r-l+1\) студент поднял руку.
- Ложно отрицательный: присутствуют \(r-l+1\) студент, но \(r-l\) студентов поднял руку.
В первых двух случаях студенты считаются отвечающими честно, в то время как в последних двух случаях студенты считаются отвечающими нечестно. Студенты могут взаимно решить свою стратегию, неизвестную мистеру 1048576. Кроме того, студенты не хотят вызывать подозрений и в то же время хотят создать много путаницы. Поэтому их стратегия всегда соответствует следующим двум условиям —
- Студенты никогда не будут отвечать честно \(3\) раза подряд.
- Студенты никогда не будут отвечать нечестно \(3\) раза подряд.
Мистер 1048576 раздосадован таким поведением студентов. Поэтому он готов отметить как минимум \(2\) студентов как отсутствующих (хотя он знает, что отсутствует только один). Посещаемость считается успешной, если отсутствующий студент находится среди этих двух. Кроме того, из-за ограниченного времени на занятия, он может задать не более \(\lceil\log_{1.116}{n}\rceil-1\) запросов (странное число, но ладно). Помогите ему завершить успешную посещаемость.
Протокол взаимодействия
Сначала прочтите строку, содержащую одно целое число \(t\) (\(1\leq t\leq 2048\)), обозначающее количество независимых тестов, которые вы должны решить.
Для каждого теста сначала прочтите строку, содержащую одно целое число \(n\) (\(3\leq n\leq 10^5\)). Затем вы можете задать до \(\lceil\log_{1.116}{n}\rceil-1\) запросов.
Чтобы задать запрос, напечатайте одну строку в формате "? l r" (без кавычек) \((1\leq l\leq r\leq n)\). Затем прочтите одну строку, содержащую одно целое число \(x\) (\(r-l\leq x\leq r-l+1\)), обозначающее количество студентов, поднявших руки в ответ на запрос.
Чтобы отметить студента как отсутствующего, напечатайте одну строку в формате "! a" (без кавычек) \((1\leq a\leq n)\). Затем прочтите одно целое число \(y\) (\(y\in\{0,1\}\)). Если студент с номером \(a\) отсутствовал, \(y=1\), в противном случае, \(y=0\). Обратите внимание, что эта операция не считается запросом, но вы можете выполнить эту операцию не более \(2\) раз.
Чтобы завершить тест, напечатайте одну строку в формате "#" (без кавычек). Затем вы должны продолжить решать оставшиеся тесты.
Обратите внимание, что если вы зададите больше запросов, или запрос будет невалидным — вы получите вердикт Wrong answer.
Гарантируется, что сумма \(n\) по всем тестам не превышает \(10^5\).
После вывода ответов не забудьте вывести конец строки и очистить буфер вывода. В противном случае вы получите вердикт Idleness limit exceeded. Чтобы очистить буфер, используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- Прочтите документацию для других языков.
Формат ввода для взломов
Тесты для этой задачи используют как неадаптивные, так и адаптивные тесты. Вы можете использовать неадаптивный тест для проведения взломов.
Первая строка ввода содержит одно целое число \(t\) (\(1\leq t\leq 2048\)).
Первая строка каждого теста содержит три целых числа \(g\), \(n\) и \(x\), где \(g=1\) (для идентификации того, что этот тест должен использовать неадаптивный алгоритм), \(n\) (\(3\leq n\leq 10^5\)) означает количество студентов в классе, и \(x\) (\(1\leq x\leq n\)) означает номер студента, который отсутствует. Вы должны учесть, что сумма \(n\) по всем тестам не превышает \(10^5\).
Вторая строка каждого теста содержит одну строку \(S\) (\(1\leq\vert S\vert\leq 120, S_i\in \{\texttt{T},\texttt{F}\}\)). Эта строка представляет последовательность истины. Если \(S_{(i-1)\bmod \vert S\vert+1}= \texttt{T}\), студенты будут действовать честно во время \(i\)-го запроса, в противном случае они будут действовать нечестно. Вы также должны учесть, что не должно быть индекса \(i\), для которого \(S_{(i-1)\bmod \vert S\vert+1} = S_{i\bmod \vert S\vert+1} = S_{(i+1)\bmod \vert S\vert+1}\).
Примечание
Для первого теста отсутствует студент с номером \(2\), и последовательность истины (см. раздел для взломов) — TFFTFTTF. Во время выполнения вашего решения этот тест будет использовать неадаптивный алгоритм.
Для второго теста отсутствует студент с номером \(4\), и последовательность истины — FFTFTTFT. Во время выполнения вашего решения этот тест будет использовать адаптивный алгоритм. Таким образом, фактический ответ может измениться в зависимости от ваших запросов, но всегда будет согласован с ответом на предыдущие запросы.