시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 28 24 23 85.185%

문제

성공한 벤쳐회사 "봉씨"의 데이터 분석원 이석원은 매일매일 전세계 사용자에 대한 정보를 받은뒤 이를 시각화한다. 이석원은 자신이 만든 시각화 툴을 이용한다.

아래 그림은 이석원의 시각화 툴을 이용해서 만든 히스토그램이다.

위의 예에서 구간 0-9는 5번 발생했고, 10-19는 3번, 20-29와 30-39는 한 번씩 발생한 것이다.

이석원의 히스토그램 생성 프로그램은 매우 간단하다. 먼저, 히스토그램의 높이는 고정되어 있다. 즉, 가장 높은 막대의 높이는 항상 일정하고, 나머지 막대의 높이는 그 막대와의 비율에 의해 정해진다. 또, 막대의 너비도 고정되어있다. 그렇기 때문에 구간의 크기는 항상 정해져 있다. (위의 그림에선 10이다) 

마지막으로, 각각의 막대는 가장 왼쪽이 검정색 (밝기: 1), 오른쪽이 흰색 (밝기: 0)이고, 그 사이 막대는 왼쪽에서 오른쪽으로 갈 수록 일정한 비율에 따라서 밝기가 감소한다. 예를 들어, 위의 그림에서 막대의 검은 정도는 1, 2/3, 1/3, 0이다.

히스토그램을 출력하는데 필요한 잉크의 양을 구하는 프로그램을 작성하시오. 각 막대를 그리는데 필요한 잉크의 양은 면적과 검은 정도에 비례한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 히스토그램의 값의 개수 n과 구간의 크기 w가 주어진다. 다음 줄에는 자료의 값이 주어진다. 첫 막대의 구간은 0 ≤ v < w, 두 번째 막대의 구간은 w ≤ v < 2w이고, 나머지 막대의 구간도 이와 같이 정할 수 있다. 어떤 막대에 포함되는 값의 개수가 0개이더라도 그 막대를 그리지 않으면 안 된다. (1 ≤ n ≤ 100, 10 ≤ w ≤ 50, 0 ≤ 값 ≤ 100)

값의 최댓값은 w보다 작지 않다. 따라서, 히스토그램은 한 개보다 많은 구간을 가지고 있다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서 히스토그램을 그리는데 필요한 잉크의 양을 출력한다.

가장 높은 막대를 검정색으로 드는데 잉크가 1만큼 필요하다. 또, 히스토그램에서 축과 글자를 그리는데 필요한 잉크의 양은 0.01이다. 예를 들어, 위에서 주어진 히스토그을 그리는데 필요한 잉크의 양은 다음과 같다.

정답과의 오차가 10-5보다 작은 경우에 정답이다.

예제 입력 1

3 50
100
0
100
3 50
100
100
50
10 10
1
2
3
4
5
16
17
18
29
30
0 0

예제 출력 1

0.51
0.26
1.4766666666666667
W3sicHJvYmxlbV9pZCI6IjM4ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2OGNcdWMwYzkgXHVjNjAxXHVjNWVkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzFcdWFjZjVcdWQ1NWMgXHViY2E0XHVjY2QwXHVkNjhjXHVjMGFjICZxdW90O1x1YmQwOVx1YzUyOCZxdW90O1x1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHViZDg0XHVjMTFkXHVjNmQwIFx1Yzc3NFx1YzExZFx1YzZkMFx1Yzc0MCBcdWI5ZTRcdWM3N2NcdWI5ZTRcdWM3N2MgXHVjODA0XHVjMTM4XHVhY2M0IFx1YzBhY1x1YzZhOVx1Yzc5MFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHViOTdjIFx1YmMxYlx1Yzc0MFx1YjRhNCBcdWM3NzRcdWI5N2MgXHVjMmRjXHVhYzAxXHVkNjU0XHVkNTVjXHViMmU0LiBcdWM3NzRcdWMxMWRcdWM2ZDBcdWM3NDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YjljY1x1YjRlMCBcdWMyZGNcdWFjMDFcdWQ2NTQgXHVkMjM0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM3NzRcdWMxMWRcdWM2ZDBcdWM3NTggXHVjMmRjXHVhYzAxXHVkNjU0IFx1ZDIzNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGUwIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXBsb2FkXC9pbWFnZXNcL2dyZS5wbmdcIiBzdHlsZT1cIndpZHRoOiAzNzBweDsgaGVpZ2h0OiAyNzNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyBcdWFkNmNcdWFjMDQgMC05XHViMjk0IDVcdWJjODggXHViYzFjXHVjMGRkXHVkNTg4XHVhY2UwLCAxMC0xOVx1YjI5NCAzXHViYzg4LCAyMC0yOVx1YzY0MCAzMC0zOVx1YjI5NCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YmMxY1x1YzBkZFx1ZDU1YyBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzExZFx1YzZkMFx1Yzc1OCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YTggXHVjMGRkXHVjMTMxIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVhYzA0XHViMmU4XHVkNTU4XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVhY2UwXHVjODE1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc3Y1x1YzgxNVx1ZDU1OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1YjljOVx1YjMwMFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVhZGY4IFx1YjljOVx1YjMwMFx1YzY0MFx1Yzc1OCBcdWJlNDRcdWM3MjhcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YzgxNVx1ZDU3NFx1YzljNFx1YjJlNC4gXHViNjEwLCBcdWI5YzlcdWIzMDBcdWM3NTggXHViMTA4XHViZTQ0XHViM2M0IFx1YWNlMFx1YzgxNVx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViODA3XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFkNmNcdWFjMDRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM4MTVcdWQ1NzRcdWM4MzggXHVjNzg4XHViMmU0LiAoXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzEyMCAxMFx1Yzc3NFx1YjJlNCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCBcdWFjMDFcdWFjMDFcdWM3NTggXHViOWM5XHViMzAwXHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmRcdWM3NzQgXHVhYzgwXHVjODE1XHVjMGM5IChcdWJjMWRcdWFlMzA6IDEpLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NzQgXHVkNzcwXHVjMGM5IChcdWJjMWRcdWFlMzA6IDApXHVjNzc0XHVhY2UwLCBcdWFkZjggXHVjMGFjXHVjNzc0IFx1YjljOVx1YjMwMFx1YjI5NCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMThcdWI4NWQgXHVjNzdjXHVjODE1XHVkNTVjIFx1YmU0NFx1YzcyOFx1YzVkMCBcdWI1MzBcdWI3N2NcdWMxMWMgXHViYzFkXHVhZTMwXHVhYzAwIFx1YWMxMFx1YzE4Y1x1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWI5YzlcdWIzMDBcdWM3NTggXHVhYzgwXHVjNzQwIFx1YzgxNVx1YjNjNFx1YjI5NCAxLCAyXC8zLCAxXC8zLCAwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3ODlcdWQwNmNcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMDEgXHViOWM5XHViMzAwXHViOTdjIFx1YWRmOFx1YjlhY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzg5XHVkMDZjXHVjNzU4IFx1YzU5MVx1Yzc0MCBcdWJhNzRcdWM4MDFcdWFjZmMgXHVhYzgwXHVjNzQwIFx1YzgxNVx1YjNjNFx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YWMxMlx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFkNmNcdWFjMDRcdWM3NTggXHVkMDZjXHVhZTMwIHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjhjY1x1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc0MCAwICZsZTsgdiAmbHQ7IHcsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc0MCB3ICZsZTsgdiAmbHQ7IDJ3XHVjNzc0XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YjNjNCBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHViOWM5XHViMzAwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWFjMTJcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIDBcdWFjMWNcdWM3NzRcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZGY4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFkZjhcdWI5YWNcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwMCwgMTAgJmxlOyB3ICZsZTsgNTAsIDAgJmxlOyBcdWFjMTIgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YWMxMlx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDAgd1x1YmNmNFx1YjJlNCBcdWM3OTFcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc0MCBcdWQ1NWMgXHVhYzFjXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWI0NTAgXHVhYzFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzg5XHVkMDZjXHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3NDAgXHViOWM5XHViMzAwXHViOTdjIFx1YWM4MFx1YzgxNVx1YzBjOVx1YzczY1x1Yjg1YyBcdWI0ZGNcdWIyOTRcdWIzNzAgXHVjNzg5XHVkMDZjXHVhYzAwIDFcdWI5Y2NcdWQwN2MgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWI2MTAsIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1YzVkMFx1YzExYyBcdWNkOTVcdWFjZmMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YWRmOFx1YjlhY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzg5XHVkMDZjXHVjNzU4IFx1YzU5MVx1Yzc0MCAwLjAxXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1Yzc0NCBcdWFkZjhcdWI5YWNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc4OVx1ZDA2Y1x1Yzc1OCBcdWM1OTFcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9pbmsucG5nXCIgc3R5bGU9XCJ3aWR0aDogMjg0cHg7IGhlaWdodDogMTA5cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YjJmNVx1YWNmY1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWFjMDAgMTA8c3VwPi01PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzODg1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3JleSBBcmVhIiwiZGVzY3JpcHRpb24iOiI8cD5Eci4gR3JleSBpcyBhIGRhdGEgYW5hbHlzdCwgd2hvIHZpc3VhbGl6ZXMgdmFyaW91cyBhc3BlY3RzIG9mIGRhdGEgcmVjZWl2ZWQgZnJvbSBhbGwgb3ZlciB0aGUgd29ybGQgZXZlcnlkYXkuIEhlIGlzIGV4dHJlbWVseSBnb29kIGF0IHNvcGhpc3RpY2F0ZWQgdmlzdWFsaXphdGlvbiB0b29scywgYnV0IHlldCBoaXMgZmF2b3JpdGUgaXMgYSBzaW1wbGUgc2VsZi1tYWRlIGhpc3RvZ3JhbSBnZW5lcmF0b3IuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ3JlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI3M3B4OyB3aWR0aDozNzBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTogQSBoaXN0b2dyYW08XC9wPlxyXG5cclxuPHA+RmlndXJlIDEgaXMgYW4gZXhhbXBsZSBvZiBoaXN0b2dyYW0gYXV0b21hdGljYWxseSBwcm9kdWNlZCBieSBoaXMgaGlzdG9ncmFtIGdlbmVyYXRvci4gQSBoaXN0b2dyYW0gaXMgYSB2aXN1YWwgZGlzcGxheSBvZiBmcmVxdWVuY2llcyBvZiB2YWx1ZSBvY2N1cnJlbmNlcyBhcyBiYXJzLiBJbiB0aGlzIGV4YW1wbGUsIHZhbHVlcyBpbiB0aGUgaW50ZXJ2YWwgMCZuZGFzaDs5IG9jY3VyIGZpdmUgdGltZXMsIHRob3NlIGluIHRoZSBpbnRlcnZhbCAxMCZuZGFzaDsxOSBvY2N1ciB0aHJlZSB0aW1lcywgYW5kIDIwJm5kYXNoOzI5IGFuZCAzMCZuZGFzaDszOSBvbmNlIGVhY2guPFwvcD5cclxuXHJcbjxwPkRyLiBHcmV5JnJzcXVvO3MgaGlzdG9ncmFtIGdlbmVyYXRvciBpcyBhIHNpbXBsZSB0b29sLiBGaXJzdCwgdGhlIGhlaWdodCBvZiB0aGUgaGlzdG9ncmFtIGlzIGZpeGVkLCB0aGF0IGlzLCB0aGUgaGVpZ2h0IG9mIHRoZSBoaWdoZXN0IGJhciBpcyBhbHdheXMgdGhlIHNhbWUgYW5kIHRob3NlIG9mIHRoZSBvdGhlcnMgYXJlIGF1dG9tYXRpY2FsbHkgYWRqdXN0ZWQgcHJvcG9ydGlvbmF0ZWx5LiBTZWNvbmQsIHRoZSB3aWR0aHMgb2YgYmFycyBhcmUgYWxzbyBmaXhlZC4gSXQgY2FuIG9ubHkgcHJvZHVjZSBhIGhpc3RvZ3JhbSBvZiB1bmlmb3JtIGludGVydmFscywgdGhhdCBpcywgZWFjaCBpbnRlcnZhbCBvZiBhIGhpc3RvZ3JhbSBzaG91bGQgaGF2ZSB0aGUgc2FtZSB3aWR0aCAoMTAgaW4gdGhlIGFib3ZlIGV4YW1wbGUpLiBGaW5hbGx5LCB0aGUgYmFyIGZvciBlYWNoIGludGVydmFsIGlzIHBhaW50ZWQgaW4gYSBncmV5IGNvbG9yLCB3aGVyZSB0aGUgY29sb3JzIG9mIHRoZSBsZWZ0bW9zdCBhbmQgdGhlIHJpZ2h0bW9zdCBpbnRlcnZhbHMgYXJlIGJsYWNrIGFuZCB3aGl0ZSwgcmVzcGVjdGl2ZWx5LCBhbmQgdGhlIGRhcmtuZXNzIG9mIGJhcnMgbW9ub3RvbmljYWxseSBkZWNyZWFzZXMgYXQgdGhlIHNhbWUgcmF0ZSBmcm9tIGxlZnQgdG8gcmlnaHQuIEZvciBpbnN0YW5jZSwgaW4gRmlndXJlIDEsIHRoZSBkYXJrbmVzcyBsZXZlbHMgb2YgdGhlIGZvdXIgYmFycyBhcmUgMSwgMlwvMywgMVwvMywgYW5kIDAsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+SW4gdGhpcyBwcm9ibGVtLCB5b3UgYXJlIHJlcXVlc3RlZCB0byBlc3RpbWF0ZSBpbmsgY29uc3VtcHRpb24gd2hlbiBwcmludGluZyBhIGhpc3RvZ3JhbSBvbiBwYXBlci4gVGhlIGFtb3VudCBvZiBpbmsgbmVjZXNzYXJ5IHRvIGRyYXcgYSBiYXIgaXMgcHJvcG9ydGlvbmFsIHRvIGJvdGggaXRzIGFyZWEgYW5kIGRhcmtuZXNzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIGRhdGFzZXRzLCBlYWNoIG9mIHdoaWNoIGNvbnRhaW5zIGludGVnZXJzIGFuZCBzcGVjaWZpZXMgYSB2YWx1ZSB0YWJsZSBhbmQgaW50ZXJ2YWxzIGZvciB0aGUgaGlzdG9ncmFtIGdlbmVyYXRvciwgaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm4gd1xyXG52PHN1Yj4xPFwvc3ViPlxyXG52PHN1Yj4yPFwvc3ViPlxyXG4uLi5cclxudjxzdWI+bjxcL3N1Yj5cclxuPFwvcHJlPlxyXG5cclxuPHA+dyBpcyB0aGUgaW50ZXJ2YWwgd2lkdGguIEEgdmFsdWUgdiBpcyBpbiB0aGUgZmlyc3QgKGkuZS4gbGVmdG1vc3QpIGludGVydmFsIGlmIDAgJmxlOyB2ICZsdDsgdywgdGhlIHNlY29uZCBvbmUgaWYgdyAmbGU7IHYgJmx0OyAydywgYW5kIHNvIG9uLiBOb3RlIHRoYXQgdGhlIGludGVydmFsIGZyb20gMCAoaW5jbHVzaXZlKSB0byB3IChleGNsdXNpdmUpIHNob3VsZCBiZSByZWdhcmRlZCBhcyB0aGUgbGVmdG1vc3QgZXZlbiBpZiBubyB2YWx1ZXMgb2NjdXIgaW4gdGhpcyBpbnRlcnZhbC4gVGhlIGxhc3QgKGkuZS4gcmlnaHRtb3N0KSBpbnRlcnZhbCBpcyB0aGUgb25lIHRoYXQgaW5jbHVkZXMgdGhlIGxhcmdlc3QgdmFsdWUgaW4gdGhlIGRhdGFzZXQuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIHRoZSBmb2xsb3dpbmcuPFwvcD5cclxuXHJcbjxwcmU+XHJcbjEgJmxlOyBuICZsZTsgMTAwXHJcbjEwICZsZTsgdyAmbGU7IDUwXHJcbjAgJmxlOyB2aSAmbGU7IDEwMCBmb3IgMSAmbGU7IGkgJmxlOyBuPFwvcHJlPlxyXG5cclxuPHA+WW91IGNhbiBhbHNvIGFzc3VtZSB0aGF0IHRoZSBtYXhpbXVtIHZhbHVlIGlzIG5vIGxlc3MgdGhhbiB3LiBUaGlzIG1lYW5zIHRoYXQgdGhlIGhpc3RvZ3JhbSBoYXMgbW9yZSB0aGFuIG9uZSBpbnRlcnZhbC48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIGFtb3VudCBvZiBpbmsgY29uc3VtZWQgaW4gcHJpbnRpbmcgdGhlIGhpc3RvZ3JhbS48XC9wPlxyXG5cclxuPHA+T25lIHVuaXQgb2YgaW5rIGlzIG5lY2Vzc2FyeSB0byBwYWludCBvbmUgaGlnaGVzdCBiYXIgYmxhY2suIEFzc3VtZSB0aGF0IDA6MDEgdW5pdHMgb2YgaW5rIHBlciBoaXN0b2dyYW0gaXMgY29uc3VtZWQgZm9yIHZhcmlvdXMgcHVycG9zZXMgZXhjZXB0IGZvciBwYWludGluZyBiYXJzIHN1Y2ggYXMgZHJhd2luZyBsaW5lcyBhbmQgY2hhcmFjdGVycyAoc2VlIEZpZ3VyZSAxKS4gRm9yIGluc3RhbmNlLCB0aGUgYW1vdW50IG9mIGluayBjb25zdW1lZCBpbiBwcmludGluZyB0aGUgaGlzdG9ncmFtIGluIEZpZ3VyZSAxIGlzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2luay5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDlweDsgd2lkdGg6Mjg0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RWFjaCBvdXRwdXQgdmFsdWUgc2hvdWxkIGJlIGluIGEgZGVjaW1hbCBmcmFjdGlvbiBhbmQgbWF5IGhhdmUgYW4gZXJyb3IgbGVzcyB0aGFuIDEwPHN1cD4mbWludXM7NTxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2008 in Aizu A번