Единственное отличие между этой задачей и другими двумя версиями — максимальное количество запросов. В этой версии вы можете сделать не более \(\mathbf{25}\) запросов. Вы можете делать взломы только в том случае, если все версии задачи решены.
Это интерактивная задача.
«Все-все! Идеальная пара Дореми по структурам данных уже начинается! Присаживайтесь и хорошо поработайте, если хотите иметь такой же IQ, как у меня!» На сегодняшней паре Дореми рассказывает о могущественной структуре данных: дереве Дореми! И прямо сейчас она дает вам задание, чтобы проверить, насколько вы внимательно слушаете.
Пусть есть массив целых чисел \(a\) длины \(m\). Дерево Дореми поддерживает запросы \(Q(l,r,k)\), где \(1 \leq l \leq r \leq m\) и \(1 \leq k \leq m\), которые возвращают количество различных целых чисел в массиве \(\left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right]\).
Дореми загадала перестановку \(p\) целых чисел от \(1\) до \(n\). Вы можете делать запросы, в одном запросе вы задаете \(3\) целых числа \(l,r,k\) (\(1 \leq l \leq r \leq n\), \(1 \leq k \leq n\)) и получаете в ответ значение \(Q(l,r,k)\) для массива \(p\). Можете ли вы найти индекс \(y\) (\(1 \leq y \leq n\)) такой, что \(p_y=1\), за не более чем \(\mathbf{25}\) запросов?
Обратите внимание, что перестановка \(p\) зафиксирована до начала взаимодействия.
Протокол взаимодействия
В начале взаимодействия считайте целое число \(n\) (\(3 \le n \le 1024\)) в первой строке — длину перестановки.
Чтобы сделать запрос, выведите
- «? \(l\ r\ k\)» (\(1 \leq l \leq r \leq n\), \(1 \leq k \leq n\))
на отдельной строке. После вывода запроса считайте целое число
\(x\) — значение
\(Q(l,r,k)\) для перестановки
\(p\). Вы можете сделать не более
\(25\) таких запросов.
Чтобы вывести ответ, выведите
- «! \(y\)» (\(1 \leq y \leq n\))
на отдельной строке, где
\(p_y=1\).
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Формат взломов
Первая строка должна содержать одно целое число \(n\) (\(3 \le n \le 1024\)) — длину перестановки.
Вторая строка должна содержать \(n\) различных целых чисел \(p_1,p_2,\ldots,p_n\) (\(1 \le p_i\le n\)) — загаданную перестановку.
Примечание
Перестановка в примере равна \([3,5,2,1,4]\).
Примеры ввода и вывода иллюстрируют возможное взаимодействие в примере (дополнительные переводы строк добавлены только для удобства чтения).
В этом взаимодействии:
- В первом запросе \(\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=0\), поэтому ответ равен \(2\).
- Во втором запросе \(\lfloor\frac{2}{3}\rfloor=0,\lfloor\frac{1}{3}\rfloor=0,\lfloor\frac{4}{3}\rfloor=1\), поэтому ответ равен \(2\).
- В третьем запросе \(\lfloor\frac{2}{5}\rfloor=0,\lfloor\frac{1}{5}\rfloor=0\), поэтому ответ равен \(1\).
- В четвертом запросе \(\lfloor\frac{2}{2}\rfloor=1,\lfloor\frac{1}{2}\rfloor=0,\lfloor\frac{4}{2}\rfloor=2\), поэтому ответ равен \(3\).
После \(4\) запросов был выведен правильный ответ, поэтому это взаимодействие будет зачтено.