시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB159635040.984%

문제

"드디어 마지막 나무다!!"

세계적인 갑부 최백준의 정원 관리사 상근이가 외친 말이었다. 백준이네 집의 입구부터 분수까지 거리는 L미터이다. 입구와 분수 사이에는 일직선 도로가 있고, 도로의 폭은 W미터이다.

백준이는 상근이에게 도로의 양쪽에 나무를 심으라고 했다. 가장 첫 나무는 도로의 시작 지점에 있어야 하고, 마지막 나무는 끝 지점에 있어야 한다. 도로의 양쪽에 있는 나무의 위치는 모두 일치해야 한다. 또, 한 쪽 면에 있는 모든 나무 사이의 거리는 같아야 한다.

상근이는 백준이의 말을 정확하게 듣지 않았고, 도로의 왼쪽에만 나무를 심었다. 상근이는 나무를 옮겨 백준이의 요구사항 대로 나무를 심으려고 한다. 백준이의 요구사항을 지키기 위해 옮겨야 하는 나무의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 심은 나무의 수 N이 주어진다. N은 짝수이며, 4보다 크거나 같고, 2000보다 작거나 같다. 다음 줄에는 두 정수 L과 W가 주어진다. (1 ≤ L ≤ 10000, 1 ≤ w ≤ 20) 다음 N개 줄에는 나무의 위치 정수 p가 한 줄에 하나씩 주어진다. (0 ≤ p ≤ L)

출력

백준이의 요구사항을 지키기 위해 옮겨야 하는 나무의 이동거리의 최솟값을 출력한다. 정답과의 절대/상대 오차가 10-6 이내인 경우에 정답으로 인정된다.

예제 입력 1

4
10 1
1
0
10
10

예제 출력 1

2.4142135624

예제 입력 2

6
10 1
0
9
3
5
5
6

예제 출력 2

9.2853832858
W3sicHJvYmxlbV9pZCI6IjUwNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjNjJlXHVhZTMwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtcdWI0ZGNcdWI1MTRcdWM1YjQgXHViOWM4XHVjOWMwXHViOWM5IFx1YjA5OFx1YmIzNFx1YjJlNCEhJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzEzOFx1YWNjNFx1YzgwMVx1Yzc3OCBcdWFjMTFcdWJkODAgXHVjZDVjXHViYzMxXHVjOTAwXHVjNzU4IFx1YzgxNVx1YzZkMCBcdWFkMDBcdWI5YWNcdWMwYWMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzY3OFx1Y2U1YyBcdWI5ZDBcdWM3NzRcdWM1YzhcdWIyZTQuIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjEyNCBcdWM5ZDFcdWM3NTggXHVjNzg1XHVhZDZjXHViZDgwXHVkMTMwIFx1YmQ4NFx1YzIxOFx1YWU0Y1x1YzljMCBcdWFjNzBcdWI5YWNcdWIyOTQgTFx1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHVhZDZjXHVjNjQwIFx1YmQ4NFx1YzIxOCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVjNzdjXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWQzZWRcdWM3NDAgV1x1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWIzYzRcdWI4NWNcdWM3NTggXHVjNTkxXHVjYWJkXHVjNWQwIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWM3M2NcdWI3N2NcdWFjZTAgXHVkNTg4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjY2FiIFx1YjA5OFx1YmIzNFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzljMFx1YzgxMFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViMDk4XHViYjM0XHViMjk0IFx1YjA1ZCBcdWM5YzBcdWM4MTBcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViM2M0XHViODVjXHVjNzU4IFx1YzU5MVx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjZTU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWQ1NWMgXHVjYWJkIFx1YmE3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YjA5OFx1YmIzNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjMzFcdWM5MDBcdWM3NzRcdWM3NTggXHViOWQwXHVjNzQ0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWI0ZTNcdWM5YzAgXHVjNTRhXHVjNTU4XHVhY2UwLCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwXHViOWNjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWM1YzhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjNjJlXHVhY2E4IFx1YmMzMVx1YzkwMFx1Yzc3NFx1Yzc1OCBcdWM2OTRcdWFkNmNcdWMwYWNcdWQ1NmQgXHViMzAwXHViODVjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjMzFcdWM5MDBcdWM3NzRcdWM3NTggXHVjNjk0XHVhZDZjXHVjMGFjXHVkNTZkXHVjNzQ0IFx1YzljMFx1ZDBhNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNjJlXHVhY2E4XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJlY1x1Yzc0MCBcdWIwOThcdWJiMzRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YmE3MCwgNFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAyMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBMXHVhY2ZjIFdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEwgJmxlOyAxMDAwMCwgMSAmbGU7IHcgJmxlOyAyMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWM3MDRcdWNlNTggXHVjODE1XHVjMjE4IHBcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHAgJmxlOyBMKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmMzMVx1YzkwMFx1Yzc3NFx1Yzc1OCBcdWM2OTRcdWFkNmNcdWMwYWNcdWQ1NmRcdWM3NDQgXHVjOWMwXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM2MmVcdWFjYThcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWM3NzRcdWIzZDlcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzgwOFx1YjMwMFwvXHVjMGMxXHViMzAwIFx1YzYyNFx1Y2MyOFx1YWMwMCAxMDxzdXA+LTY8XC9zdXA+IFx1Yzc3NFx1YjBiNFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODE1XHViMmY1XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxNVx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1MDQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXNwZW4gQXZlbnVlIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtQaGV3LCB0aGF0IHdhcyB0aGUgbGFzdCBvbmUhJnF1b3Q7IGV4Y2xhaW1lZCB0aGUgZ2FyZGVuIGhlbHBlciBUaW0gYXMgaGUgdGhyZXcgdGhlIGxhc3QgdHJlZSBwbGFudCB0byB0aGUgZ3JvdW5kLiBIaXMgZW1wbG95ZXIsIGNvdW50ZXNzIEVzbWVyYWxkYSBIdW50IHdobyBvd25lZCB0aGUgZXN0YXRlLCBoYXMgb3JkZXJlZCBoaW0gdG8gYXJyYW5nZSBhbiBhdmVudWUgb2YgYXNwZW4gdHJlZXMgYWxvbmcgYm90aCBzaWRlcyBvZiB0aGUgZnJvbnQgcm9hZCBsZWFkaW5nIHVwIHRvIHRoZSBob3VzZS4gVGhlIGZpcnN0IHRyZWVzIGluIHRoZSBhdmVudWUgYXJlIHN1cHBvc2VkIHRvIGJlIHBsYW50ZWQgYXQgdGhlIHZlcnkgYmVnaW5uaW5nIG9mIHRoZSByb2FkLCBhbmQgdGhlIGxhc3QgdHJlZXMgb2YgdGhlIGF2ZW51ZSBhdCB0aGUgdmVyeSBlbmQgb2YgdGhlIHJvYWQuIFRpbSwgd2hvIHdhcyBjb25zdGFudGx5IGJlaW5nIHJlbWluZGVkIG9mIGhlciBzZW5zZSBvZiBhY2N1cmFjeSwga25ldyB0aGF0IHRoZSBjb3VudGVzcyB3b3VsZCBpbnNpc3Qgb24gdGhlIHRyZWVzIGJlaW5nIHBsYWNlZCBpbiBwZXJmZWN0bHkgYWxpZ25lZCB0cmVlIHBhaXJzLCBvbmUgb24gZWFjaCBzaWRlIG9mIHRoZSByb2FkLCBhbmQgd2l0aCBleGFjdGx5IHRoZSBzYW1lIHNwYWNpbmcgYmV0d2VlbiB0aGUgcGFpcnMgYWxvbmcgdGhlIHJvYWQuIEhvd2V2ZXIsIHdoZW4gYnJpbmdpbmcgdGhlIHRyZWUgcGxhbnRzIHRvIHRoZSBlc3RhdGUsIFRpbSBoYWQganVzdCBkcm9wcGVkIHRoZW0gYXJiaXRyYXJpbHkgYWxvbmcgdGhlIGxlZnQgc2lkZSBvZiB0aGUgcm9hZCBhbmQgd2FzIG5vdyBmYWNpbmcgdGhlIHRhc2sgb2YgbW92aW5nIHRoZSB0cmVlcyB0byB0aGVpciBjb3JyZWN0IHBvc2l0aW9ucyB0byBtZWV0IHRoZSBjb3VudGVzcyYjMzk7cyByZXF1aXJlbWVudHMuIEJlaW5nIHN0cm9uZ2VyIGluIG1pbmQgdGhhbiBpbiBhcm1zLCBhbmQgc2luY2UgaXQgd2FzIHRpbWUgZm9yIGEgY28gZWUgYnJlYWsgYW55d2F5IGJlZm9yZSBoZSBzdGFydGVkIGRpZ2dpbmcsIGhlIHNhdCBkb3duIHRvIGZpZ3VyZSBvdXQgd2hpY2ggdHJlZXMgdG8gbW92ZSB0byB3aGljaCBwb3NpdGlvbnMgc28gYXMgdG8gbWluaW1pemUgdGhlIHRvdGFsIChFdWNsaWRlYW4pIGRpc3RhbmNlIHRoYXQgaGUgaGFkIHRvIG1vdmUgdGhlIHRyZWVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgcG9zaXRpdmUgZXZlbiBpbnRlZ2VyIE4gYmV0d2VlbiA0IGFuZCAyMDAwIChpbmNsdXNpdmUpLCBnaXZpbmcgdGhlIHRvdGFsIG51bWJlciBvZiB0cmVlcyBpbiB0aGUgYXZlbnVlLiBUaGUgbmV4dCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBMIGFuZCBXLCB3aGVyZSAxICZsZTsgTCAmbGU7IDEwMDAwIGlzIHRoZSBsZW5ndGggb2YgdGhlIHJvYWQsIGluIG1ldGVycywgYW5kIDEgJmxlOyBXICZsZTsgMjAgaXMgdGhlIHdpZHRoIG9mIHRoZSByb2FkLCBpbiBtZXRlcnMuIFRoZSBuZXh0IE4gbGluZXMgZWFjaCBkZXNjcmliZSB3aGVyZSBUaW0gaGFkIGRyb3BwZWQgb2YgdGhlIHRyZWVzLiBFYWNoIHN1Y2ggbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIDAgJmxlOyBwICZsZTsgTCBpbmRpY2F0aW5nIHRoZSBwb3NpdGlvbiBvZiBhIHRyZWUgcGxhbnQgYWxvbmcgdGhlIGxlZnQgc2lkZSBvZiB0aGUgcm9hZCwgbWVhc3VyZWQgaW4gbWV0ZXJzIGZyb20gdGhlIHN0YXJ0IG9mIHRoZSByb2FkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIHNtYWxsZXN0IHRvdGFsIG51bWJlciBvZiBtZXRlcnMgdGhlIHRyZWUgcGxhbnRzIG5lZWQgdG8gYmUgbW92ZWQuIFRoZSBhbnN3ZXIgc2hvdWxkIGJlIGdpdmVuIHdpdGggYW4gYWJzb2x1dGUgb3IgcmVsYXRpdmUgZXJyb3Igb2YgYXQgbW9zdCAxMDxzdXA+LTY8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2008 A번