How Does Your Garden Grow?

About half of all domestic water use goes to watering gardens. During a drought a city therefore restricts watering lawns and gardens. Under such a restriction you have to decide carefully how near or far from the sprinkler each plant sits, so that every plant gets as close as possible to the right amount of water. This problem is a simplified version of that optimization.

You have $n$ plants. Each plant is a horizontal segment 1 metre long and has a known water requirement. You choose where along the line to put each plant. Plants cannot overlap, and the left end of each plant must be aligned with a multiple of 10 centimetres. For instance, you could put one plant at $[0.4, 1.4]$ and another at $[1.7, 2.7]$. You cannot put a plant at $[0.35, 1.35]$, which is not aligned, or at $[-0.5, 0.5]$, which would cover the sprinkler, and you cannot put two plants at $[0.4, 1.4]$ and $[0.7, 1.7]$, which overlap. No plant may cover the origin, so every left end is at least 0.

The water comes from a sprinkler installed at the origin $(0, 0)$. The sprinkler emits a steady stream of water at a speed of $v$ metres per second. The angle $\alpha$ at which the water leaves varies over time. It starts at $\alpha = 45^\circ$ and rotates at a uniform angular speed of $1^\circ$ per second until it reaches $\alpha = 90^\circ$ after 45 seconds, then it stops. $\alpha$ is the angle between the water direction and the ground, just like a real lawn sprinkler. While rotating, the sprinkler emits 1 unit of water per second.

The angular speed is uniform, but the amount of water that hits different parts of the ground is not. Places far enough from the sprinkler get no water at all, and the places that do get water get different amounts. A plant placed on $[a, a+1]$ collects all the water that hits that interval.

For each plant $i$ you are given the total amount $w_i$ of water it is supposed to get. Giving a plant too little water is bad, and so is giving it too much. If plant $i$ receives $w'_i$ units of water, its suffering is $(w_i - w'_i)^2$. Find a placement that minimizes the total suffering of the plants.

Your calculations need the gravitational acceleration. Use $9.81\ \text{m/s}^2$. A more or less precise value produces different results and is judged wrong. Assume water behaves like a perfect particle in a vacuum, with no friction. You may also need some trigonometric identities. Here are a few that can help.

• $\sin(\alpha + \beta) = \sin\alpha\cos\beta + \sin\beta\cos\alpha$
• $\cos(\alpha + \beta) = \cos\alpha\cos\beta - \sin\alpha\sin\beta$
• $\sin\alpha\cos\beta = \tfrac{1}{2}\left(\sin(\alpha + \beta) + \sin(\alpha - \beta)\right)$
• $\sin\alpha\sin\beta = \tfrac{1}{2}\left(\cos(\alpha - \beta) - \cos(\alpha + \beta)\right)$
• $\cos\alpha\cos\beta = \tfrac{1}{2}\left(\cos(\alpha - \beta) + \cos(\alpha + \beta)\right)$

The first line is the number $K$ of data sets. The $K$ data sets follow, each in the form below.

The first line of a data set contains the number of plants $n$ ($1 \le n \le 50$) and the water speed $v$ ($0.0 < v \le 50.0$, in metres per second), separated by a space. $v$ is a real number.

The next $n$ lines each contain the water requirement $w_i$ ($w_i \ge 0$) of one plant, one per line. $w_i$ is a real number.

For each data set, output Data Set x: on a line by itself, where $x$ is the number of the data set counting from 1.

Then output on a line by itself the smallest total suffering over all legal placements, that is placements aligned to a multiple of 10 centimetres and free of overlap, with exactly two digits after the decimal point.

Follow each data set with one blank line.