April Fools Day Contest 2023 |
---|
Закончено |
Это интерактивная задача.
У вас спрятан массив $$$a_1, a_2, \dots, a_n$$$ из $$$n$$$ целых чисел. Ваша задача — найти наименьший элемент массива.
Для этого вы можете задать несколько запросов. В каждом запросе вы можете выбрать два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). В ответ вам будет дано значение $$$\max(a_l, a_{l+1}, \dots, a_r)$$$. Иными словами, вам сообщат максимальное значение подмассива от $$$a_l$$$ до $$$a_r$$$.
Найдите минимум массива. Вы можете задать не более $$$\mathbf{624}$$$ запросов.
Гарантируется, что значения $$$a_1, a_2, \dots, a_n$$$ выбираются равномерно случайным образом в диапазоне от $$$0$$$ до $$$2^{32}-1$$$ (включительно).
Начните взаимодействие, прочитав целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) на отдельной строке.
Чтобы задать запрос, напечатайте строку в формате $$$\texttt{?}\;\;l\;\;r$$$ ($$$1 \le l \le r \le n$$$). Затем вы должны прочитать одну строку, содержащую ответ на ваш запрос.
После того, как вы определите ответ, напечатайте строку в формате $$$\texttt{!}\;\;x$$$, где $$$x$$$ — минимальное значение.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
3 1295320727 984617979 1295320727 167316954
? 1 3 ? 1 1 ? 2 2 ? 3 3 ! 167316954
Название |
---|