시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 21 20 86.957%

문제

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

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

위의 예에서 구간 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+XHJcblxyXG48cD5cdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3ODlcdWQwNmNcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMDEgXHViOWM5XHViMzAwXHViOTdjIFx1YWRmOFx1YjlhY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzg5XHVkMDZjXHVjNzU4IFx1YzU5MVx1Yzc0MCBcdWJhNzRcdWM4MDFcdWFjZmMgXHVhYzgwXHVjNzQwIFx1YzgxNVx1YjNjNFx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YWMxMlx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFkNmNcdWFjMDRcdWM3NTggXHVkMDZjXHVhZTMwIHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjhjY1x1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc0MCAwICZsZTsgdiAmbHQ7IHcsIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZDZjXHVhYzA0XHVjNzQwIHcgJmxlOyB2ICZsdDsgMndcdWM3NzRcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZDZjXHVhYzA0XHViM2M0IFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWI5YzlcdWIzMDBcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YWMxMlx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgMFx1YWMxY1x1Yzc3NFx1YjM1NFx1Yjc3Y1x1YjNjNCBcdWFkZjggXHViOWM5XHViMzAwXHViOTdjIFx1YWRmOFx1YjlhY1x1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiAoMSAmbGU7IG4gJmxlOyAxMDAsIDEwICZsZTsgdyAmbGU7IDUwLCAwICZsZTsgXHVhYzEyICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWFjMTJcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQwIHdcdWJjZjRcdWIyZTQgXHVjNzkxXHVjOWMwIFx1YzU0YVx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDAgXHVkNTVjIFx1YWMxY1x1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVhZDZjXHVhYzA0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDc4OFx1YzJhNFx1ZDFhMFx1YWRmOFx1YjdhOFx1Yzc0NCBcdWFkZjhcdWI5YWNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc4OVx1ZDA2Y1x1Yzc1OCBcdWM1OTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFjODBcdWM4MTVcdWMwYzlcdWM3M2NcdWI4NWMgXHViNGRjXHViMjk0XHViMzcwIFx1Yzc4OVx1ZDA2Y1x1YWMwMCAxXHViOWNjXHVkMDdjIFx1ZDU0NFx1YzY5NFx1ZDU1OFx1YjJlNC4gXHViNjEwLCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM1ZDBcdWMxMWMgXHVjZDk1XHVhY2ZjIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWFkZjhcdWI5YWNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzc4OVx1ZDA2Y1x1Yzc1OCBcdWM1OTFcdWM3NDAgMC4wMVx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWM3NDQgXHVhZGY4XHViOWFjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3ODlcdWQwNmNcdWM3NTggXHVjNTkxXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaW5rLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDI4NHB4OyBoZWlnaHQ6IDEwOXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWIyZjVcdWFjZmNcdWM3NTggXHVjNjI0XHVjYzI4XHVhYzAwIDEwPHN1cD4tNTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdyZXkgQXJlYSIsImRlc2NyaXB0aW9uIjoiPHA+RHIuIEdyZXkgaXMgYSBkYXRhIGFuYWx5c3QsIHdobyB2aXN1YWxpemVzIHZhcmlvdXMgYXNwZWN0cyBvZiBkYXRhIHJlY2VpdmVkIGZyb20gYWxsIG92ZXIgdGhlIHdvcmxkIGV2ZXJ5ZGF5LiBIZSBpcyBleHRyZW1lbHkgZ29vZCBhdCBzb3BoaXN0aWNhdGVkIHZpc3VhbGl6YXRpb24gdG9vbHMsIGJ1dCB5ZXQgaGlzIGZhdm9yaXRlIGlzIGEgc2ltcGxlIHNlbGYtbWFkZSBoaXN0b2dyYW0gZ2VuZXJhdG9yLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2dyZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNzNweDsgd2lkdGg6MzcwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IEEgaGlzdG9ncmFtPFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxIGlzIGFuIGV4YW1wbGUgb2YgaGlzdG9ncmFtIGF1dG9tYXRpY2FsbHkgcHJvZHVjZWQgYnkgaGlzIGhpc3RvZ3JhbSBnZW5lcmF0b3IuIEEgaGlzdG9ncmFtIGlzIGEgdmlzdWFsIGRpc3BsYXkgb2YgZnJlcXVlbmNpZXMgb2YgdmFsdWUgb2NjdXJyZW5jZXMgYXMgYmFycy4gSW4gdGhpcyBleGFtcGxlLCB2YWx1ZXMgaW4gdGhlIGludGVydmFsIDAmbmRhc2g7OSBvY2N1ciBmaXZlIHRpbWVzLCB0aG9zZSBpbiB0aGUgaW50ZXJ2YWwgMTAmbmRhc2g7MTkgb2NjdXIgdGhyZWUgdGltZXMsIGFuZCAyMCZuZGFzaDsyOSBhbmQgMzAmbmRhc2g7Mzkgb25jZSBlYWNoLjxcL3A+XHJcblxyXG48cD5Eci4gR3JleSZyc3F1bztzIGhpc3RvZ3JhbSBnZW5lcmF0b3IgaXMgYSBzaW1wbGUgdG9vbC4gRmlyc3QsIHRoZSBoZWlnaHQgb2YgdGhlIGhpc3RvZ3JhbSBpcyBmaXhlZCwgdGhhdCBpcywgdGhlIGhlaWdodCBvZiB0aGUgaGlnaGVzdCBiYXIgaXMgYWx3YXlzIHRoZSBzYW1lIGFuZCB0aG9zZSBvZiB0aGUgb3RoZXJzIGFyZSBhdXRvbWF0aWNhbGx5IGFkanVzdGVkIHByb3BvcnRpb25hdGVseS4gU2Vjb25kLCB0aGUgd2lkdGhzIG9mIGJhcnMgYXJlIGFsc28gZml4ZWQuIEl0IGNhbiBvbmx5IHByb2R1Y2UgYSBoaXN0b2dyYW0gb2YgdW5pZm9ybSBpbnRlcnZhbHMsIHRoYXQgaXMsIGVhY2ggaW50ZXJ2YWwgb2YgYSBoaXN0b2dyYW0gc2hvdWxkIGhhdmUgdGhlIHNhbWUgd2lkdGggKDEwIGluIHRoZSBhYm92ZSBleGFtcGxlKS4gRmluYWxseSwgdGhlIGJhciBmb3IgZWFjaCBpbnRlcnZhbCBpcyBwYWludGVkIGluIGEgZ3JleSBjb2xvciwgd2hlcmUgdGhlIGNvbG9ycyBvZiB0aGUgbGVmdG1vc3QgYW5kIHRoZSByaWdodG1vc3QgaW50ZXJ2YWxzIGFyZSBibGFjayBhbmQgd2hpdGUsIHJlc3BlY3RpdmVseSwgYW5kIHRoZSBkYXJrbmVzcyBvZiBiYXJzIG1vbm90b25pY2FsbHkgZGVjcmVhc2VzIGF0IHRoZSBzYW1lIHJhdGUgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBGb3IgaW5zdGFuY2UsIGluIEZpZ3VyZSAxLCB0aGUgZGFya25lc3MgbGV2ZWxzIG9mIHRoZSBmb3VyIGJhcnMgYXJlIDEsIDJcLzMsIDFcLzMsIGFuZCAwLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSwgeW91IGFyZSByZXF1ZXN0ZWQgdG8gZXN0aW1hdGUgaW5rIGNvbnN1bXB0aW9uIHdoZW4gcHJpbnRpbmcgYSBoaXN0b2dyYW0gb24gcGFwZXIuIFRoZSBhbW91bnQgb2YgaW5rIG5lY2Vzc2FyeSB0byBkcmF3IGEgYmFyIGlzIHByb3BvcnRpb25hbCB0byBib3RoIGl0cyBhcmVhIGFuZCBkYXJrbmVzcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSBkYXRhc2V0cywgZWFjaCBvZiB3aGljaCBjb250YWlucyBpbnRlZ2VycyBhbmQgc3BlY2lmaWVzIGEgdmFsdWUgdGFibGUgYW5kIGludGVydmFscyBmb3IgdGhlIGhpc3RvZ3JhbSBnZW5lcmF0b3IsIGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5uIHdcclxudjxzdWI+MTxcL3N1Yj5cclxudjxzdWI+MjxcL3N1Yj5cclxuLi4uXHJcbnY8c3ViPm48XC9zdWI+XHJcbjxcL3ByZT5cclxuXHJcbjxwPncgaXMgdGhlIGludGVydmFsIHdpZHRoLiBBIHZhbHVlIHYgaXMgaW4gdGhlIGZpcnN0IChpLmUuIGxlZnRtb3N0KSBpbnRlcnZhbCBpZiAwICZsZTsgdiAmbHQ7IHcsIHRoZSBzZWNvbmQgb25lIGlmIHcgJmxlOyB2ICZsdDsgMncsIGFuZCBzbyBvbi4gTm90ZSB0aGF0IHRoZSBpbnRlcnZhbCBmcm9tIDAgKGluY2x1c2l2ZSkgdG8gdyAoZXhjbHVzaXZlKSBzaG91bGQgYmUgcmVnYXJkZWQgYXMgdGhlIGxlZnRtb3N0IGV2ZW4gaWYgbm8gdmFsdWVzIG9jY3VyIGluIHRoaXMgaW50ZXJ2YWwuIFRoZSBsYXN0IChpLmUuIHJpZ2h0bW9zdCkgaW50ZXJ2YWwgaXMgdGhlIG9uZSB0aGF0IGluY2x1ZGVzIHRoZSBsYXJnZXN0IHZhbHVlIGluIHRoZSBkYXRhc2V0LjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGUgZm9sbG93aW5nLjxcL3A+XHJcblxyXG48cHJlPlxyXG4xICZsZTsgbiAmbGU7IDEwMFxyXG4xMCAmbGU7IHcgJmxlOyA1MFxyXG4wICZsZTsgdmkgJmxlOyAxMDAgZm9yIDEgJmxlOyBpICZsZTsgbjxcL3ByZT5cclxuXHJcbjxwPllvdSBjYW4gYWxzbyBhc3N1bWUgdGhhdCB0aGUgbWF4aW11bSB2YWx1ZSBpcyBubyBsZXNzIHRoYW4gdy4gVGhpcyBtZWFucyB0aGF0IHRoZSBoaXN0b2dyYW0gaGFzIG1vcmUgdGhhbiBvbmUgaW50ZXJ2YWwuPFwvcD5cclxuXHJcbjxwPlRoZSBlbmQgb2YgdGhlIGlucHV0IGlzIGluZGljYXRlZCBieSBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIHRoZSBhbW91bnQgb2YgaW5rIGNvbnN1bWVkIGluIHByaW50aW5nIHRoZSBoaXN0b2dyYW0uPFwvcD5cclxuXHJcbjxwPk9uZSB1bml0IG9mIGluayBpcyBuZWNlc3NhcnkgdG8gcGFpbnQgb25lIGhpZ2hlc3QgYmFyIGJsYWNrLiBBc3N1bWUgdGhhdCAwOjAxIHVuaXRzIG9mIGluayBwZXIgaGlzdG9ncmFtIGlzIGNvbnN1bWVkIGZvciB2YXJpb3VzIHB1cnBvc2VzIGV4Y2VwdCBmb3IgcGFpbnRpbmcgYmFycyBzdWNoIGFzIGRyYXdpbmcgbGluZXMgYW5kIGNoYXJhY3RlcnMgKHNlZSBGaWd1cmUgMSkuIEZvciBpbnN0YW5jZSwgdGhlIGFtb3VudCBvZiBpbmsgY29uc3VtZWQgaW4gcHJpbnRpbmcgdGhlIGhpc3RvZ3JhbSBpbiBGaWd1cmUgMSBpczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9pbmsucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTA5cHg7IHdpZHRoOjI4NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkVhY2ggb3V0cHV0IHZhbHVlIHNob3VsZCBiZSBpbiBhIGRlY2ltYWwgZnJhY3Rpb24gYW5kIG1heSBoYXZlIGFuIGVycm9yIGxlc3MgdGhhbiAxMDxzdXA+Jm1pbnVzOzU8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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