Problem E
Gradient Descent

The goal is to minimize a function $f(x)$ by changing $x$, where $x$ is usually a scalar or a vector. In machine learning, $x$ often represents the parameters of the learning model, and $f$ represents the error function (such as squared error).

The gradient descent method uses $f’$ (the first derivative of $f$). If $x$ is a vector, then $f’$ is a vector of partial derivatives, so that

With an initial guess $x_0$, gradient descent repeatedly applies the following rule:

for a user-chosen parameter $\alpha $, called the step size. In this manner, each initial $x_0$ will eventually lead to a (local) minimum of the function.

For this problem, implement gradient descent in an interactive setting. Your submission queries the grader by proposing different values of $x$, and for each $x$ proposed it receives back two pieces of information: the values $f(x)$ and $f’(x)$.

Input

Your submission is run interactively, meaning that it determines when to quit (within the time limit). Initially your submission reads three lines:

• an integer $d$ ($1 \le d \le 10$) representing the dimension of the parameter space,

• a list $L$ of $d$ real numbers representing the least values of the parameter space, and

• a list $G$ of $d$ real numbers representing the greatest values of the parameter space.

The values of $L$ and $G$ are all in the range $[-1\, 000, 1\, 000]$. After this, for every query $x$ your submission produces, the grader responds with two lines:

• a single real number representing $f(x)$, and

• a list of $d$ real numbers representing $f’(x)$.

Additionally, the following guarantees hold:

• All real numbers in the input have at most $6$ digits after the decimal point.

• Every value of $f(x)$ is in the range $[1, 10^6]$.

• The function $f$ is continuous and differentiable in the ranges given.

Output

The output of your submission must be one line per query $x$, each line containing $d$ real numbers. The real numbers must be in the bounds given ($L$ and $G$) or the submission is considered incorrect. Your submission may make up to $10\, 000$ queries per test case. Since this is an interactive problem, your submission should flush its output buffer with every query (e.g. cout << flush in C++, or sys.stdout.flush() in Python).

Scoring

For each test case, the interactive validator keeps track of the lowest value $f(x)$ observed for any query $x$ your submission produces. Let this value be called $p$, and let the judge’s minimum value of $f$ be called $j$. The score your submission receives is

and is clamped to the range $[0, 100]$. If your submission makes too many queries, no queries, or an incorrect query, then the submission is judged as incorrect.

The total score your submission gets is the average of all $s$ over all hidden test cases.