시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 687 | 208 | 136 | 27.309% |
선영이는 정말 환상적인 지도 앱을 만들고 있다. 지도 앱의 이름은 Moogle Maps이며, Maple mPhone에 탑재될 예정이다. 이 앱은 "Main Street 13"과 같은 도로명 주소의 위치를 가리킬 수 있는 기능이 있다. 하지만, mPhone의 저장 용량은 제한되어 있다. 따라서, 선영이는 데이터의 양을 줄어야 한다.
조금 생각해보니 모든 번지의 위치를 정확하게 저장할 필요는 없다고 생각했다. 그 대신, 일부 번지의 주소만 정확하게 탑재한 다음, 나머지는 선형 보간법 (linearly interpolated)을 이용해서 사용하려고 한다. 이때, 정확한 집의 위치와 선형 보간법을 사용해 계산한 집의 위치 사이의 오차의 평균값을 최소가 되도록 저장하는 번지의 위치를 선택하려고 한다.
길은 일직선으로 나타낼 수 있고, 첫 번째 집과 마지막 집의 위치는 항상 저장한다.
번지가 i인 집의 위치 xi와 j인 집의 위치 xj를 저장했고, 그 사이의 집은 저장하지 않았을 때, 번지가 k (i < k < j)인 집의 위치를 선형 보간법으로 계산하면 xi + (xj-xi) * (k-i)/(j-i)가 된다.
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50)
각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 집의 수 h와 저장할 수 있는 집 위치의 수 c가 주어진다. (2 ≤ h ≤ 200, 2 ≤ c ≤ h) 둘째 줄에는 각각의 집의 위치가 주어진다. 위치는 구간 [0, 1000000]에 포함된다.
각 테스트 케이스에 대해서, h개의 집 중 오차의 평균이 최소가 되도록 c개의 집의 위치를 저장했을 때, 그 오차의 평균을 출력한다. 출력은 소수점 넷째자리까지 하며, 오차는 ±0.001까지 허용한다.
2 4 3 0 9 20 40 10 4 0 10 19 30 40 90 140 190 202 210
0.2500 0.3000
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2007 I번