Автор задачи: Егор Юлин, разработчик: Константин Бац
Это довольно классическая задача на двоичный поиск. Как видно в этой задаче, двоичный поиск можно применять не только в массиве отсортированных в каком-либо порядке объектов, но и по произвольным другим монотонным критериям.
Наша цель — найти величину «сдвига» $$$c$$$, с которым нам сообщается информация. Если внимательно посмотреть на $$$f(x)$$$ и мысленно выписать $$$f(1), f(2), \ldots, f(n)$$$, можно заметить, что получится осортированный массив $$$a_i$$$, циклически сдвинутый на величину $$$c$$$, то есть $$$[a_{c+1}, \ldots, a_n, a_1, \ldots, a_c]$$$. Иными словами, это два отсортированных массива $$$[a_{c+1}, \ldots, a_n]$$$ и $$$a_1, \ldots, a_c$$$, выписанные подряд. Плюс, стоит не забывать, что $$$a_{c+1} > a_c$$$, то есть все элементы левой части больше всех элементов правой.
Этим критерием мы и воспользуемся. Запросим у интерактора значение $$$y = f(0)$$$ — это наш $$$a_{c+1}$$$. Заметим, что все элементы левой части (до $$$a_n$$$) не меньше $$$y$$$, а правой — наоборот, меньше. Таким образом, у нас теперь есть монотонный критерий, по которому можно делать бинпоиск: выберем $$$m$$$ на середине текущего отрезка, и проверим:
В конце $$$l$$$ и $$$r$$$ будут соседними, но в разных частях, то есть $$$l = n - c$$$ и $$$r = n - c + 1$$$. Зная эти значения и число $$$n$$$, мы можем спокойно восстановить ответ. Для этого нам понадобилось всего либо $$$\left\lceil \log_2 (n - 1) \right\rceil + 1$$$ запросов, что с большим запасом укладывается в ограничения задачи.