정원에 물 주기

가정에서 쓰는 물의 약 절반은 정원에 물을 주는 데 들어간다. 그래서 가뭄이 오면 도시는 잔디와 정원에 물 주는 것을 제한한다. 이런 제한이 걸린 동안에는 각 식물을 스프링클러에서 얼마나 가깝게 또는 멀게 놓을지 신중하게 정해서, 필요한 양에 최대한 가까운 물을 받게 해야 한다. 이 문제는 그 최적화를 단순하게 만든 것이다.

식물이 $n$개 있다. 각 식물은 길이 1미터의 수평 선분이고, 필요한 물의 양이 정해져 있다. 정할 것은 각 식물을 직선 위 어디에 놓을지다. 식물끼리 겹칠 수 없고, 각 식물의 왼쪽 끝은 10센티미터의 배수에 맞춰야 한다. 예를 들어 한 식물을 $[0.4, 1.4]$에, 다른 식물을 $[1.7, 2.7]$에 놓을 수 있다. 하지만 $[0.35, 1.35]$는 10센티미터의 배수에 맞지 않아 놓을 수 없고, $[-0.5, 0.5]$는 스프링클러 위를 덮으므로 놓을 수 없고, $[0.4, 1.4]$와 $[0.7, 1.7]$은 서로 겹치므로 함께 놓을 수 없다. 원점을 덮을 수 없으니 왼쪽 끝은 항상 0 이상이다.

물은 원점 $(0, 0)$에 설치된 스프링클러에서 나온다. 스프링클러는 초속 $v$미터의 일정한 속력으로 물을 뿜는다. 물이 나가는 각도 $\alpha$는 시간에 따라 변한다. $\alpha = 45^\circ$에서 시작해 초당 $1^\circ$의 일정한 각속도로 회전하고, 45초 뒤 $\alpha = 90^\circ$에 닿으면 멈춘다. $\alpha$는 물이 나가는 방향과 지면이 이루는 각이다. 실제 잔디용 스프링클러와 같은 방식이다. 회전하는 동안 물은 초당 1단위씩 나온다.

각속도는 일정하지만 지면의 각 부분에 떨어지는 물의 양은 일정하지 않다. 스프링클러에서 충분히 먼 곳에는 물이 아예 닿지 않고, 물이 닿는 곳도 받는 양이 서로 다르다. 그래서 식물을 놓을 자리를 잘 골라야 한다. 구간 $[a, a+1]$에 놓인 식물은 그 구간에 떨어지는 물을 모두 모은다.

식물 $i$가 받아야 하는 물의 총량 $w_i$가 주어진다. 물을 너무 적게 주는 것도 나쁘고 너무 많이 주는 것도 나쁘다. 식물 $i$가 물 $w'_i$를 받으면 그 식물의 고통은 $(w_i - w'_i)^2$이다. 모든 식물의 고통의 합이 가장 작아지는 배치를 찾아라.

계산에는 중력 가속도가 필요하다. 값은 $9.81\ \text{m/s}^2$을 쓴다. 더 정밀한 값이나 덜 정밀한 값을 쓰면 결과가 달라져 틀린 답이 된다. 물은 마찰 같은 것이 없는 진공에서 완전한 입자처럼 움직인다고 가정한다. 삼각함수 공식이 필요할 수도 있다. 쓸 만한 것을 몇 개 적어 둔다.

• $\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)$

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 집합의 첫 줄에는 식물의 개수 $n$ ($1 \le n \le 50$)과 물의 속력 $v$ ($0.0 < v \le 50.0$, 단위는 m/s)가 공백으로 구분되어 주어진다. $v$는 실수다.

이어지는 $n$개의 줄에는 각 식물이 필요한 물의 양 $w_i$ ($w_i \ge 0$)가 한 줄에 하나씩 주어진다. $w_i$는 실수다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 집합의 번호이고 1부터 센다.

그 다음 줄에 규칙을 지키는 배치, 즉 10센티미터의 배수에 맞고 서로 겹치지 않는 배치 중에서 고통의 합이 가장 작은 값을 소수점 아래 둘째 자리까지 출력한다.

각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.