322. Безградиентная оптимизация функции

Это интерактивная задача

Человечество получило в своё распоряжение мощнейший инструмент, позволяющий измерять высоту относительно уровня моря. С его помощью можно обнаружить все горные пики на нашей планете.

Вам наверняка хочется назвать какой-нибудь пик в свою честь. Вы даже знаете, где его искать. Но есть загвоздка: инструмент измеряет высоту только в заданной точке, а число попыток ограничено.

Более формально, есть функция от двух аргументов $f(x, y)$, заданная на квадрате $[-50; 100] \times [-50; 100]$, обладающая липшицевым градиентом и имеющая несколько точек локального максимума $(x_1^{*}, y_1^{*}), \dots (x_k^{*}, y_k^{*})$. Сам вид функции и число точек локального максимума неизвестны, гарантируется лишь, что все точки локального максимума лежат в квадрате $[0;50] \times [0;50]$. При поиске локального максимума программа может делать запрос о величине функции в определенной точке.

Требуется найти один из локальных максимумов, сделав не более 200 запросов.

В первой строке входных данных будут находиться три вещественных числа $X_0, Y_0, H_0$ ($-50 \le X_0 \le 100$, $-50 \le Y_0 \le 100$), где $X_0$ и $Y_0$ — координаты стартовой точки, от которой имеет смысл начинать поиск, а $H_0$ — значение $f(X_0, Y_0)$.

Чтобы узнать значение функции $f$ в очередной точке $(X_i, Y_i)$, выведите строку, содержащую координаты этой точки, разделённые пробелом — вида $X_i$ $Y_i$. После этого выведите перевод строки и сделайте операцию flush.

Замечание: если ваша точка лежит вне квадрата $[-50; 100] \times [-50; 100]$, вы получите вердикт <<Неправильный формат вывода>>

После выполнения запроса на вход вашей программе будет подана информация о значении функции в текущей точке, а также информация о том, находится ли данная точка достаточно близко к некоторому локальному максимуму. Обозначим за $h_i$ значение функции в текущей точке. Возможны два варианта:

• Если расстояние от заданной вами точки до ближайшего локального максимума больше $10^{-2}$, то на входе будет строка вида "$-\ h_i$" (минус ('-') и значение функции, разделённые пробелом).
• Если расстояние от заданной вами точки до ближайшего локального максимума не больше $10^{-2}$, то на входе будет строка вида "$+\ h_i$" (плюс ('+') и значение функции, разделённые пробелом).

В последнем случае ваша программа должна немедленно завершиться (например, вызовом exit(0)).

Замечание: значение функции выводится с точностью $10^{-8}$.

Если ваша программа не смогла за 200 запросов найти одну из точек локального максимума, то вы получите вердикт <<Неправильный ответ>>.

Ваше решение получит вердикт <<Решение зависло>> (IL), если вы не будете ничего выводить или забудете сделать операцию flush после вывода запроса.

Чтобы выполнить операцию flush, можете использовать (сразу после вывода запроса и перевода строки):

• fflush(stdout) в C++
• sys.stdout.flush() в Python

Ниже показан пример взаимодействия программы и интерактора.

В данном случае программа сделала 4 запроса, причем последняя точка оказалась достаточно близко к некоторой точке локального максимума. Обнаружив это, программа ничего не выводит, а завершается с кодом возврата 0.