시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 22 21 84.000%

문제

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

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

위의 예에서 구간 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+XHJcblxyXG48cD5cdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3ODlcdWQwNmNcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMDEgXHViOWM5XHViMzAwXHViOTdjIFx1YWRmOFx1YjlhY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzg5XHVkMDZjXHVjNzU4IFx1YzU5MVx1Yzc0MCBcdWJhNzRcdWM4MDFcdWFjZmMgXHVhYzgwXHVjNzQwIFx1YzgxNVx1YjNjNFx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzU4IFx1YWMxMlx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFkNmNcdWFjMDRcdWM3NTggXHVkMDZjXHVhZTMwIHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YjhjY1x1Yzc1OCBcdWFjMTJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc0MCAwICZsZTsgdiAmbHQ7IHcsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1Yzc0MCB3ICZsZTsgdiAmbHQ7IDJ3XHVjNzc0XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHViOWM5XHViMzAwXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YjNjNCBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHViOWM5XHViMzAwXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWFjMTJcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIDBcdWFjMWNcdWM3NzRcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZGY4IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWFkZjhcdWI5YWNcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwLCAxMCAmbGU7IHcgJmxlOyA1MCwgMCAmbGU7IFx1YWMxMiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0MCB3XHViY2Y0XHViMmU0IFx1Yzc5MVx1YzljMCBcdWM1NGFcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDU1YyBcdWFjMWNcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQwIFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ3ODhcdWMyYTRcdWQxYTBcdWFkZjhcdWI3YThcdWM3NDQgXHVhZGY4XHViOWFjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3ODlcdWQwNmNcdWM3NTggXHVjNTkxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YjE5Mlx1Yzc0MCBcdWI5YzlcdWIzMDBcdWI5N2MgXHVhYzgwXHVjODE1XHVjMGM5XHVjNzNjXHViODVjIFx1YjRkY1x1YjI5NFx1YjM3MCBcdWM3ODlcdWQwNmNcdWFjMDAgMVx1YjljY1x1ZDA3YyBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YjYxMCwgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHViN2E4XHVjNWQwXHVjMTFjIFx1Y2Q5NVx1YWNmYyBcdWFlMDBcdWM3OTBcdWI5N2MgXHVhZGY4XHViOWFjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM3ODlcdWQwNmNcdWM3NTggXHVjNTkxXHVjNzQwIDAuMDFcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNzg4XHVjMmE0XHVkMWEwXHVhZGY4XHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjNzg5XHVkMDZjXHVjNzU4IFx1YzU5MVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2luay5wbmdcIiBzdHlsZT1cIndpZHRoOiAyODRweDsgaGVpZ2h0OiAxMDlweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YWMwMCAxMDxzdXA+LTU8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjODE1XHViMmY1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHcmV5IEFyZWEiLCJkZXNjcmlwdGlvbiI6IjxwPkRyLiBHcmV5IGlzIGEgZGF0YSBhbmFseXN0LCB3aG8gdmlzdWFsaXplcyB2YXJpb3VzIGFzcGVjdHMgb2YgZGF0YSByZWNlaXZlZCBmcm9tIGFsbCBvdmVyIHRoZSB3b3JsZCBldmVyeWRheS4gSGUgaXMgZXh0cmVtZWx5IGdvb2QgYXQgc29waGlzdGljYXRlZCB2aXN1YWxpemF0aW9uIHRvb2xzLCBidXQgeWV0IGhpcyBmYXZvcml0ZSBpcyBhIHNpbXBsZSBzZWxmLW1hZGUgaGlzdG9ncmFtIGdlbmVyYXRvci48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ncmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjczcHg7IHdpZHRoOjM3MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBBIGhpc3RvZ3JhbTxcL3A+XHJcblxyXG48cD5GaWd1cmUgMSBpcyBhbiBleGFtcGxlIG9mIGhpc3RvZ3JhbSBhdXRvbWF0aWNhbGx5IHByb2R1Y2VkIGJ5IGhpcyBoaXN0b2dyYW0gZ2VuZXJhdG9yLiBBIGhpc3RvZ3JhbSBpcyBhIHZpc3VhbCBkaXNwbGF5IG9mIGZyZXF1ZW5jaWVzIG9mIHZhbHVlIG9jY3VycmVuY2VzIGFzIGJhcnMuIEluIHRoaXMgZXhhbXBsZSwgdmFsdWVzIGluIHRoZSBpbnRlcnZhbCAwJm5kYXNoOzkgb2NjdXIgZml2ZSB0aW1lcywgdGhvc2UgaW4gdGhlIGludGVydmFsIDEwJm5kYXNoOzE5IG9jY3VyIHRocmVlIHRpbWVzLCBhbmQgMjAmbmRhc2g7MjkgYW5kIDMwJm5kYXNoOzM5IG9uY2UgZWFjaC48XC9wPlxyXG5cclxuPHA+RHIuIEdyZXkmcnNxdW87cyBoaXN0b2dyYW0gZ2VuZXJhdG9yIGlzIGEgc2ltcGxlIHRvb2wuIEZpcnN0LCB0aGUgaGVpZ2h0IG9mIHRoZSBoaXN0b2dyYW0gaXMgZml4ZWQsIHRoYXQgaXMsIHRoZSBoZWlnaHQgb2YgdGhlIGhpZ2hlc3QgYmFyIGlzIGFsd2F5cyB0aGUgc2FtZSBhbmQgdGhvc2Ugb2YgdGhlIG90aGVycyBhcmUgYXV0b21hdGljYWxseSBhZGp1c3RlZCBwcm9wb3J0aW9uYXRlbHkuIFNlY29uZCwgdGhlIHdpZHRocyBvZiBiYXJzIGFyZSBhbHNvIGZpeGVkLiBJdCBjYW4gb25seSBwcm9kdWNlIGEgaGlzdG9ncmFtIG9mIHVuaWZvcm0gaW50ZXJ2YWxzLCB0aGF0IGlzLCBlYWNoIGludGVydmFsIG9mIGEgaGlzdG9ncmFtIHNob3VsZCBoYXZlIHRoZSBzYW1lIHdpZHRoICgxMCBpbiB0aGUgYWJvdmUgZXhhbXBsZSkuIEZpbmFsbHksIHRoZSBiYXIgZm9yIGVhY2ggaW50ZXJ2YWwgaXMgcGFpbnRlZCBpbiBhIGdyZXkgY29sb3IsIHdoZXJlIHRoZSBjb2xvcnMgb2YgdGhlIGxlZnRtb3N0IGFuZCB0aGUgcmlnaHRtb3N0IGludGVydmFscyBhcmUgYmxhY2sgYW5kIHdoaXRlLCByZXNwZWN0aXZlbHksIGFuZCB0aGUgZGFya25lc3Mgb2YgYmFycyBtb25vdG9uaWNhbGx5IGRlY3JlYXNlcyBhdCB0aGUgc2FtZSByYXRlIGZyb20gbGVmdCB0byByaWdodC4gRm9yIGluc3RhbmNlLCBpbiBGaWd1cmUgMSwgdGhlIGRhcmtuZXNzIGxldmVscyBvZiB0aGUgZm91ciBiYXJzIGFyZSAxLCAyXC8zLCAxXC8zLCBhbmQgMCwgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0sIHlvdSBhcmUgcmVxdWVzdGVkIHRvIGVzdGltYXRlIGluayBjb25zdW1wdGlvbiB3aGVuIHByaW50aW5nIGEgaGlzdG9ncmFtIG9uIHBhcGVyLiBUaGUgYW1vdW50IG9mIGluayBuZWNlc3NhcnkgdG8gZHJhdyBhIGJhciBpcyBwcm9wb3J0aW9uYWwgdG8gYm90aCBpdHMgYXJlYSBhbmQgZGFya25lc3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgZGF0YXNldHMsIGVhY2ggb2Ygd2hpY2ggY29udGFpbnMgaW50ZWdlcnMgYW5kIHNwZWNpZmllcyBhIHZhbHVlIHRhYmxlIGFuZCBpbnRlcnZhbHMgZm9yIHRoZSBoaXN0b2dyYW0gZ2VuZXJhdG9yLCBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdC48XC9wPlxyXG5cclxuPHByZT5cclxubiB3XHJcbnY8c3ViPjE8XC9zdWI+XHJcbnY8c3ViPjI8XC9zdWI+XHJcbi4uLlxyXG52PHN1Yj5uPFwvc3ViPlxyXG48XC9wcmU+XHJcblxyXG48cD53IGlzIHRoZSBpbnRlcnZhbCB3aWR0aC4gQSB2YWx1ZSB2IGlzIGluIHRoZSBmaXJzdCAoaS5lLiBsZWZ0bW9zdCkgaW50ZXJ2YWwgaWYgMCAmbGU7IHYgJmx0OyB3LCB0aGUgc2Vjb25kIG9uZSBpZiB3ICZsZTsgdiAmbHQ7IDJ3LCBhbmQgc28gb24uIE5vdGUgdGhhdCB0aGUgaW50ZXJ2YWwgZnJvbSAwIChpbmNsdXNpdmUpIHRvIHcgKGV4Y2x1c2l2ZSkgc2hvdWxkIGJlIHJlZ2FyZGVkIGFzIHRoZSBsZWZ0bW9zdCBldmVuIGlmIG5vIHZhbHVlcyBvY2N1ciBpbiB0aGlzIGludGVydmFsLiBUaGUgbGFzdCAoaS5lLiByaWdodG1vc3QpIGludGVydmFsIGlzIHRoZSBvbmUgdGhhdCBpbmNsdWRlcyB0aGUgbGFyZ2VzdCB2YWx1ZSBpbiB0aGUgZGF0YXNldC48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhlIGZvbGxvd2luZy48XC9wPlxyXG5cclxuPHByZT5cclxuMSAmbGU7IG4gJmxlOyAxMDBcclxuMTAgJmxlOyB3ICZsZTsgNTBcclxuMCAmbGU7IHZpICZsZTsgMTAwIGZvciAxICZsZTsgaSAmbGU7IG48XC9wcmU+XHJcblxyXG48cD5Zb3UgY2FuIGFsc28gYXNzdW1lIHRoYXQgdGhlIG1heGltdW0gdmFsdWUgaXMgbm8gbGVzcyB0aGFuIHcuIFRoaXMgbWVhbnMgdGhhdCB0aGUgaGlzdG9ncmFtIGhhcyBtb3JlIHRoYW4gb25lIGludGVydmFsLjxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG91dHB1dCBhIGxpbmUgY29udGFpbmluZyB0aGUgYW1vdW50IG9mIGluayBjb25zdW1lZCBpbiBwcmludGluZyB0aGUgaGlzdG9ncmFtLjxcL3A+XHJcblxyXG48cD5PbmUgdW5pdCBvZiBpbmsgaXMgbmVjZXNzYXJ5IHRvIHBhaW50IG9uZSBoaWdoZXN0IGJhciBibGFjay4gQXNzdW1lIHRoYXQgMDowMSB1bml0cyBvZiBpbmsgcGVyIGhpc3RvZ3JhbSBpcyBjb25zdW1lZCBmb3IgdmFyaW91cyBwdXJwb3NlcyBleGNlcHQgZm9yIHBhaW50aW5nIGJhcnMgc3VjaCBhcyBkcmF3aW5nIGxpbmVzIGFuZCBjaGFyYWN0ZXJzIChzZWUgRmlndXJlIDEpLiBGb3IgaW5zdGFuY2UsIHRoZSBhbW91bnQgb2YgaW5rIGNvbnN1bWVkIGluIHByaW50aW5nIHRoZSBoaXN0b2dyYW0gaW4gRmlndXJlIDEgaXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaW5rLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwOXB4OyB3aWR0aDoyODRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5FYWNoIG91dHB1dCB2YWx1ZSBzaG91bGQgYmUgaW4gYSBkZWNpbWFsIGZyYWN0aW9uIGFuZCBtYXkgaGF2ZSBhbiBlcnJvciBsZXNzIHRoYW4gMTA8c3VwPiZtaW51czs1PFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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