10458번 - How Does Your Garden Grow? 다국어

About 50% of domestic water usage results from people watering their gardens. As a result, during droughts, cities tend to put into effect restrictions on watering lawns and gardens. When such a restriction is in place, you need to carefully allocate which plants go how close or far from the sprinkler, to make sure they get as close as possible to the right amount of water. Here, you will investigate a simplified version of this optimization problem.

You have n plants, each of which is modeled as a horizontal line of length 1 meter, and each of which has a known need for water. Your choice is where along the line to place each of the plants. They cannot overlap, and we will assume that each plant must be aligned with a multiple of 10 centimeters. That is, for instance, you could place one plant at the interval [0.4, 1.4], and another at [1.7, 2.7], but you cannot place one at [0.35, 1.35] (not correctly aligned) or [−0.5, 0.5] (cannot put on top of the sprinkler), or two plants at [0.4, 1.4] and [0.7, 1.7] (overlap).

Where does the water come from? There is a sprinkler installed at the origin of the line, coordinate (0, 0). The sprinkler emits a steady stream of water at velocity, measured in meters per second. The angle at which the water is emitted varies over time: the sprinkler starts at an angle of α = 45^◦ and rotates at a uniform angular speed of 1^◦ per second until it hits the angle α = 90^◦ (after 45 seconds); then it stops. α is the angle between the water direction and the ground. This is very much like a real lawn sprinkler. (See the figure.) While rotating, it emits water at a rate of 1 unit of water per second.

Figure 2: A schematic drawing of the lawn sprinkler. The dashed lines indicate the legal angle range. The dotted line shows the water’s path. The sold line shows the direction the sprinkler is aimed.

While the angular speed is uniform over time, the amount of water that hits different parts of the ground is not. So you need to carefully choose where to place your plants. Some places (far enough from the sprinkler) will not be hit by any water; others will get different amounts of water. Any interval [a, a + 1] will collect all the water that hits that interval for that plant. For each plant i, you will be given the total amount w_i of water it is supposed to be given. Giving a plant too little water is bad, but so is giving it too much water. If you give plant i w′_i units of water, but it wanted w_i, its suffering is (w_i − w′_i)². Your goal is to find a placement minimizing the total suffering of your plants.

In your calculations, you will likely need the Earth’s gravity acceleration. For your calculations, please use 9.81 m/s² ; if you use more or less precision, your results will differ from ours and be judged wrong. Assume that water behaves like a perfect particle without any friction or such in a vacuum. You might also find a need for some trigonometry formulas. Here are some of the possibly useful ones:

• sin(α + β) = sin(α) cos(β) + sin(β) cos(α),
• cos(α + β) = cos(α) cos(β) − sin(α) sin(β),
• sin(α) cos(β) = 1/2 · (sin(α + β) + sin(α − β)),
• sin(α) sin(β) = 1/2 · (cos(α − β) − cos(α + β)),
• cos(α) cos(β) = 1/2 · (cos(α − β) + cos(α + β)).

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line contains an integer 1 ≤ n ≤ 50 (the number of plants you have) and a double 0.0 < v ≤ 50.0 (the water velocity in meters per second).

This is followed by n lines, each giving you the water requirement w_i ≥ 0 (a double) of that plant.

For each data set, output “Data Set x:” on a line by itself, where x is its number.

Then, output on a line by itself the minimum suffering of your plants in the best possible legal (aligned and non-overlapping) placement.

Each data set should be followed by a blank line.