시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 524 157 92 24.865%

문제

선영이는 정말 환상적인 지도 앱을 만들고 있다. 지도 앱의 이름은 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까지 허용한다.

예제 입력 1

2
4 3
0 9 20 40
10 4
0 10 19 30 40 90 140 190 202 210

예제 출력 1

0.2500
0.3000

힌트

W3sicHJvYmxlbV9pZCI6IjUwNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWFlMDAgXHViOWY1XHVjMmE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjODE1XHViOWQwIFx1ZDY1OFx1YzBjMVx1YzgwMVx1Yzc3OCBcdWM5YzBcdWIzYzQgXHVjNTcxXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNCBcdWM1NzFcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIE1vb2dsZSBNYXBzXHVjNzc0XHViYTcwLCBNYXBsZSBtUGhvbmVcdWM1ZDAgXHVkMGQxXHVjN2FjXHViNDIwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzU3MVx1Yzc0MCAmcXVvdDtNYWluIFN0cmVldCAxMyZxdW90O1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViM2M0XHViODVjXHViYTg1IFx1YzhmY1x1YzE4Y1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzAwXHViOWFjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHViMmE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBtUGhvbmVcdWM3NTggXHVjODAwXHVjN2E1IFx1YzZhOVx1YjdjOVx1Yzc0MCBcdWM4MWNcdWQ1NWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YzkwNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg3MFx1YWUwOCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWIyYzggXHViYWE4XHViNGUwIFx1YmM4OFx1YzljMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YzgwMFx1YzdhNVx1ZDU2MCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC4gXHVhZGY4IFx1YjMwMFx1YzJlMCwgXHVjNzdjXHViZDgwIFx1YmM4OFx1YzljMFx1Yzc1OCBcdWM4ZmNcdWMxOGNcdWI5Y2MgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1ZDBkMVx1YzdhY1x1ZDU1YyBcdWIyZTRcdWM3NGMsIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBcdWMxMjBcdWQ2MTUgXHViY2Y0XHVhYzA0XHViYzk1IChsaW5lYXJseSBpbnRlcnBvbGF0ZWQpXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM4MTVcdWQ2NTVcdWQ1NWMgXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWMxMjBcdWQ2MTUgXHViY2Y0XHVhYzA0XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NCBcdWFjYzRcdWMwYjBcdWQ1NWMgXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjNjI0XHVjYzI4XHVjNzU4IFx1ZDNjOVx1YWRlMFx1YWMxMlx1Yzc0NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWJjODhcdWM5YzBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWUzOFx1Yzc0MCBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOWQxXHVhY2ZjIFx1YjljOFx1YzljMFx1YjljOSBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM4MDBcdWM3YTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4OFx1YzljMFx1YWMwMCBpXHVjNzc4IFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNTggeDxzdWI+aTxcL3N1Yj5cdWM2NDAgalx1Yzc3OCBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4IHg8c3ViPmo8XC9zdWI+XHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU4OFx1YWNlMCwgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM5ZDFcdWM3NDAgXHVjODAwXHVjN2E1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU1OFx1Yzc0NCBcdWI1NGMsIFx1YmM4OFx1YzljMFx1YWMwMCBrIChpICZsdDsgayAmbHQ7IGopXHVjNzc4IFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjMTIwXHVkNjE1IFx1YmNmNFx1YWMwNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWJhNzQgeDxzdWI+aTxcL3N1Yj4gKyAoeDxzdWI+ajxcL3N1Yj4teDxzdWI+aTxcL3N1Yj4pICogKGstaSlcLyhqLWkpXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgdCAmbGU7IDUwKTxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWQxXHVjNzU4IFx1YzIxOCBoXHVjNjQwIFx1YzgwMFx1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzlkMSBcdWM3MDRcdWNlNThcdWM3NTggXHVjMjE4IGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IGggJmxlOyAyMDAsIDIgJmxlOyBjICZsZTsgaCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWFkNmNcdWFjMDQgWzAsIDEwMDAwMDBdXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIGhcdWFjMWNcdWM3NTggXHVjOWQxIFx1YzkxMSBcdWM2MjRcdWNjMjhcdWM3NTggXHVkM2M5XHVhZGUwXHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgY1x1YWMxY1x1Yzc1OCBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWM2MjRcdWNjMjhcdWM3NTggXHVkM2M5XHVhZGUwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVjNzQwIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWIxMzdcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVkNTU4XHViYTcwLCBcdWM2MjRcdWNjMjhcdWIyOTQgJnBsdXNtbjswLjAwMVx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTA2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vb2dsZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGdvdCB0aGUgb3JpZ2luYWwgaWRlYSBvZiBtYWtpbmcgbWFwIHNvZnR3YXJlLCBjYWxsZWQgTW9vZ2xlIE1hcHMsIGZvciB0aGUgbmV3IGNvb2wgTWFwbGUgbVBob25lLiBJdCB3aWxsIGV2ZW4gYmUgY2FwYWJsZSBvZiBpbmRpY2F0aW5nIHRoZSBsb2NhdGlvbiBvZiBhIGhvdXNlIGFkZHJlc3MgbGlrZSAmcmRxdW87TWFpbiBTdHJlZXQgMTMmcmRxdW87LiBIb3dldmVyLCBzaW5jZSB0aGUgbVBob25lIGhhcyBsaW1pdGVkIHN0b3JhZ2UgY2FwYWNpdHksIHlvdSBuZWVkIHRvIHJlZHVjZSB0aGUgZGF0YSBhbW91bnQuIFlvdSBkb24mcnNxdW87dCB3YW50IHRvIHN0b3JlIHRoZSBleGFjdCBsb2NhdGlvbiBvZiBldmVyeSBzaW5nbGUgaG91c2UgbnVtYmVyLiBJbnN0ZWFkIG9ubHkgYSBzdWJzZXQgb2YgdGhlIGhvdXNlIG51bWJlcnMgd2lsbCBiZSBzdG9yZWQgZXhhY3RseSwgYW5kIHRoZSBvdGhlcnMgd2lsbCBiZSBsaW5lYXJseSBpbnRlcnBvbGF0ZWQuIFNvIHlvdSB3YW50IHRvIHNlbGVjdCBob3VzZSBudW1iZXJzIHRoYXQgd2lsbCBtaW5pbWlzZSB0aGUgYXZlcmFnZSBpbnRlcnBvbGF0aW9uIGVycm9yLCBnaXZlbiBob3cgbWFueSBob3VzZSBsb2NhdGlvbnMgeW91IGhhdmUgY2FwYWNpdHkgdG8gc3RvcmUuIFdlIHZpZXcgdGhlIHN0cmVldCBhcyBhIHN0cmFpZ2h0IGxpbmUsIGFuZCB5b3Ugd2lsbCBhbHdheXMgc3RvcmUgdGhlIFx1ZmIwMXJzdCBhbmQgdGhlIGxhc3QgaG91c2UgbG9jYXRpb24uPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoYXQgeW91JnJzcXVvO3ZlIHN0b3JlZCB0aGUgbG9jYXRpb25zIHg8c3ViPmk8XC9zdWI+IGFuZCB4PHN1Yj5qPFwvc3ViPiBmb3IgdGhlIGhvdXNlcyB3aXRoIG51bWJlcnMgaSBhbmQgaiByZXNwZWN0aXZlbHksIGJ1dCBubyBvdGhlciBob3VzZSBpbiBiZXR3ZWVuLCB0aGUgaW50ZXJwb2xhdGVkIHZhbHVlIGZvciBhIGhvdXNlIHdpdGggbnVtYmVyIGsgd2l0aCBpICZsdDsgayAmbHQ7IGogaXMmbmJzcDt4PHN1Yj5pPFwvc3ViPiZuYnNwOysgKHg8c3ViPmo8XC9zdWI+LXg8c3ViPmk8XC9zdWI+KSAqIChrLWkpXC8oai1pKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGdpdmVzIGEgc2luZ2xlIGludGVnZXIsIDEgJmxlOyB0ICZsZTsgNTAsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy48XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGVyZSBhcmUgdHdvIGxpbmVzLiBUaGUgZmlyc3QgY29udGFpbnMgMiAmbGU7IGggJmxlOyAyMDAgYW5kIDIgJmxlOyBjICZsZTsgaCwgd2hlcmUgaCBpcyB0aGUgbnVtYmVyIG9mIGhvdXNlcyBpbiB0aGUgc3RyZWV0IGFuZCBjIGlzIHRoZSBudW1iZXIgb2YgaG91c2UgbG9jYXRpb25zIHRoYXQgY2FuIGJlIHN0b3JlZC4gVGhlIHNlY29uZCBjb250YWlucyBoIGludGVnZXJzIGluIGluY3JlYXNpbmcgb3JkZXIgZ2l2aW5nIHRoZSBsb2NhdGlvbiBvZiB0aGUgaCBob3VzZXMuIEVhY2ggbG9jYXRpb24gaXMgaW4gdGhlIGludGVydmFsIFswLCAxMDAwMDAwXS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgYXZlcmFnZSBpbnRlcnBvbGF0aW9uIGVycm9yIG92ZXIgYWxsIHRoZSBoIGhvdXNlcyBmb3IgdGhlIG9wdGltYWwgc2VsZWN0aW9uIG9mIGMgaG91c2UgbG9jYXRpb25zIHRvIHN0b3JlLiBUaGUgb3V0cHV0IHNob3VsZCBiZSBnaXZlbiB3aXRoIGZvdXIgZGVjaW1hbCBwbGFjZXMsIGJ1dCB3ZSB3aWxsIGFjY2VwdCBpbmFjY3VyYWNpZXMgb2YgdXAgdG8gJnBsdXNtbjswLjAwMS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=