Задача A. Нули функции с монотонным профилем

Автор:А. Баранов   Ограничение времени:1 сек
Ввод / вывод:интерактивный   Ограничение памяти:2 Мб

Условие

Данная задача является интерактивной и предполагает взаимодействие с сервером путем отправки и приема сообщений определенного вида.

Пусть имеется функция F(x1, x2, …, xn), которая в некоторой заданной области D = [a1, b1] × [a2, b2] × … × [an, bn] обладает монотонным профилем по каждой из осей координат. Иначе говоря, если зафиксировать любые n1 из ее аргументов, то мы получим монотонную функцию одной переменной. Примером такой функции (в случае трех переменных) является: F(x1, x2, x3) = (x1 + x2) ⋅ x3.

Требуется найти любую такую точку x = (x1, x2, …, xn) из D, в которой исходная функция принимает заданное значение f0. При этом погрешность решения должна составлять не более, чем 109.

В качестве погрешности решения здесь будем рассматривать величину следующего вида:

Er = miny ∈ S(maxi|xi − yi|), где S = {y ∈ D: F(y) = f0} — область точных решений.

Протокол взаимодействия

Взаимодействие с сервером происходит посредством следующих команд, которые выводятся в выходной поток (stdout).

При первом запросе в выходной поток необходимо вывести команду:

run

В качестве ответа через входной поток (stdin) будет получено натуральное n — число аргументов целевой функции, за которым следуют n пар вещественных чисел [ai, bi], определяющих диапазон изменений каждого i-го аргумента, и значение f0.

Для вычисления функции в заданной точке, используется команда:

get, за которой следует набор из n вещественных аргументов (отделенных друг от друга пробелами).

В качестве ответа будет отправлено полученное значение.

Данная команда приводит к возникновению ошибки, если заданная точка лежит за пределами допустимой области.

Если решение было найдено, сеанс должен быть завершен командой:

ans, за которой следует набор из n вещественных значений, определяющих искомую точку.

В противном случае, сеанс завершается командой:

not

Ограничения

Для корректной работы программы, после каждой команды, отправленной в выходной поток, следует осуществлять вывод перевода строки и выполнять сброс буфера (flush). Общее число запросов к серверу не должно превышать 1100.

Все вещественные значения указываются с точностью до 10-го знака после запятой.

0 ≤ (bi − ai) ≤ 10, 0 < n ≤ 10


0.071s 0.021s 15