Codeforces Global Round 24 |
---|
Закончено |
Единственное отличие между этой задачей и другими двумя версиями — максимальное количество запросов. В этой версии вы можете сделать не более $$$\mathbf{20}$$$ запросов. Вы можете делать взломы только в том случае, если все версии задачи решены.
Это интерактивная задача.
«Все-все! Идеальная пара Дореми по структурам данных уже начинается! Присаживайтесь и хорошо поработайте, если хотите иметь такой же 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{20}$$$ запросов?
Обратите внимание, что перестановка $$$p$$$ зафиксирована до начала взаимодействия.
В начале взаимодействия считайте целое число $$$n$$$ ($$$3 \le n \le 1024$$$) в первой строке — длину перестановки.
Чтобы сделать запрос, выведите
Чтобы вывести ответ, выведите
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Формат взломов
Первая строка должна содержать одно целое число $$$n$$$ ($$$3 \le n \le 1024$$$) — длину перестановки.
Вторая строка должна содержать $$$n$$$ различных целых чисел $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i\le n$$$) — загаданную перестановку.
5 2 2 1 3
? 1 3 4 ? 3 5 3 ? 3 4 5 ? 3 5 2 ! 4
Перестановка в примере равна $$$[3,5,2,1,4]$$$.
Примеры ввода и вывода иллюстрируют возможное взаимодействие в примере (дополнительные переводы строк добавлены только для удобства чтения).
В этом взаимодействии:
После $$$4$$$ запросов был выведен правильный ответ, поэтому это взаимодействие будет зачтено.
Название |
---|