문제
히바이는 최근에 만든 예술 작품을 광고하기 위해 별점을 조작하려고 한다. 물론 없는 별점을 막 만들었다가는 당연히 조작이 들통날 것이기 때문에, 별점의 평균만을 사용하여 작품의 별점을 조작하기로 했다.
- 우선 히바이는 자신의 작품에 매겨진 $N$개의 별점을 모두 담은 리스트를 만든다.
- 이후, 리스트에 정확히 1ドル$개의 별점이 남을 때까지 아래 과정을 반복한다.
- 리스트에 있는 별점 중 2ドル$개 이상을 선택한다.
- 선택한 별점을 리스트에서 삭제한 뒤, 선택한 별점의 평균을 리스트에 추가한다.
- 위 과정을 끝낸 뒤 최종적으로 리스트에 남아있는 별점이 작품의 별점이 된다.
위와 같은 방식으로 작품의 별점을 조작할 때 히바이가 얻을 수 있는 작품의 별점의 최댓값을 구해 보자.
출력
첫째 줄에 히바이가 얻을 수 있는 작품의 별점의 최댓값을 출력한다.
실제 정답과 출력한 값의 절대오차 또는 상대오차가 10ドル^{-9}$ 이하이면 정답으로 처리된다.
만약 3ドル$개의 별점을 모두 선택해서 평균을 낸다면 작품의 별점은 20ドル$점이 된다.
하지만 10ドル$점과 20ドル$점을 먼저 선택한 뒤 평균을 내서 15ドル$점을 만들고, 이와 30ドル$점의 평균을 내면 작품의 별점을 22ドル.5$점으로 만들 수 있다.
W3sicHJvYmxlbV9pZCI6IjM0MDIwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiW01dIE1lYW5pbmcgb2YgYW4gQXZlcmFnZSIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNzg4XHViYzE0XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWI5Y2NcdWI0ZTAgXHVjNjA4XHVjMjIwIFx1Yzc5MVx1ZDQ4OFx1Yzc0NCBcdWFkMTFcdWFjZTBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmNjNFx1YzgxMFx1Yzc0NCBcdWM4NzBcdWM3OTFcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAgXHVjNWM2XHViMjk0IFx1YmNjNFx1YzgxMFx1Yzc0NCBcdWI5YzkgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0XHVhYzAwXHViMjk0IFx1YjJmOVx1YzVmMFx1ZDc4OCBcdWM4NzBcdWM3OTFcdWM3NzQgXHViNGU0XHVkMWI1XHViMGEwIFx1YWM4M1x1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmNjNFx1YzgxMFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWI5Y2NcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTU4XHVjNWVjIFx1Yzc5MVx1ZDQ4OFx1Yzc1OCBcdWJjYzRcdWM4MTBcdWM3NDQgXHVjODcwXHVjNzkxXHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM2YjBcdWMxMjAgXHVkNzg4XHViYzE0XHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM3OTFcdWQ0ODhcdWM1ZDAgXHViOWU0XHVhY2E4XHVjOWM0ICROJFx1YWMxY1x1Yzc1OCBcdWJjYzRcdWM4MTBcdWM3NDQgXHViYWE4XHViNDUwIFx1YjJmNFx1Yzc0MCBcdWI5YWNcdWMyYTRcdWQyYjhcdWI5N2MgXHViOWNjXHViNGUwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWQ2YzQsIFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMCBcdWM4MTVcdWQ2NTVcdWQ3ODggJDEkXHVhYzFjXHVjNzU4IFx1YmNjNFx1YzgxMFx1Yzc3NCBcdWIwYThcdWM3NDQgXHViNTRjXHVhZTRjXHVjOWMwIFx1YzU0NFx1Yjc5OCBcdWFjZmNcdWM4MTVcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5cdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmNjNFx1YzgxMCBcdWM5MTEgJDIkXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0XHQ8bGk+XHVjMTIwXHVkMGRkXHVkNTVjIFx1YmNjNFx1YzgxMFx1Yzc0NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjMGFkXHVjODFjXHVkNTVjIFx1YjRhNCwgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YmNjNFx1YzgxMFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NDQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwIFx1Y2Q5NFx1YWMwMFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+XHVjNzA0IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWIwNWRcdWIwYjggXHViNGE0IFx1Y2Q1Y1x1Yzg4NVx1YzgwMVx1YzczY1x1Yjg1YyBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDAgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YmNjNFx1YzgxMFx1Yzc3NCBcdWM3OTFcdWQ0ODhcdWM3NTggXHViY2M0XHVjODEwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3OTFcdWQ0ODhcdWM3NTggXHViY2M0XHVjODEwXHVjNzQ0IFx1Yzg3MFx1Yzc5MVx1ZDU2MCBcdWI1NGMgXHVkNzg4XHViYzE0XHVjNzc0XHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc5MVx1ZDQ4OFx1Yzc1OCBcdWJjYzRcdWM4MTBcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNjNFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZSBOXFxsZSAyMDBcXCwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkTiRcdWFjMWNcdWM3NTggXHViY2M0XHVjODEwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWM4MTVcdWMyMTggJEFfMSxBXzIsXFxsZG90cyAsQV9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgwXFxsZSBBX2lcXGxlIDEwXjkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNzg4XHViYzE0XHVjNzc0XHVhYzAwIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yzc5MVx1ZDQ4OFx1Yzc1OCBcdWJjYzRcdWM4MTBcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmU0XHVjODFjIFx1YzgxNVx1YjJmNVx1YWNmYyBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVhYzEyXHVjNzU4IFx1YzgwOFx1YjMwMFx1YzYyNFx1Y2MyOCBcdWI2MTBcdWIyOTQgXHVjMGMxXHViMzAwXHVjNjI0XHVjYzI4XHVhYzAwICQxMF57LTl9JCBcdWM3NzRcdWQ1NThcdWM3NzRcdWJhNzQgXHVjODE1XHViMmY1XHVjNzNjXHViODVjIFx1Y2M5OFx1YjlhY1x1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHViOWNjXHVjNTdkICQzJFx1YWMxY1x1Yzc1OCBcdWJjYzRcdWM4MTBcdWM3NDQgXHViYWE4XHViNDUwIFx1YzEyMFx1ZDBkZFx1ZDU3NFx1YzExYyBcdWQzYzlcdWFkZTBcdWM3NDQgXHViMGI4XHViMmU0XHViYTc0IFx1Yzc5MVx1ZDQ4OFx1Yzc1OCBcdWJjYzRcdWM4MTBcdWM3NDAgJDIwJFx1YzgxMFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyAkMTAkXHVjODEwXHVhY2ZjICQyMCRcdWM4MTBcdWM3NDQgXHViYTNjXHVjODAwIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWI0YTQgXHVkM2M5XHVhZGUwXHVjNzQ0IFx1YjBiNFx1YzExYyAkMTUkXHVjODEwXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCwgXHVjNzc0XHVjNjQwICQzMCRcdWM4MTBcdWM3NTggXHVkM2M5XHVhZGUwXHVjNzQ0IFx1YjBiNFx1YmE3NCBcdWM3OTFcdWQ0ODhcdWM3NTggXHViY2M0XHVjODEwXHVjNzQ0ICQyMi41JFx1YzgxMFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzNDAyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IltNXSBNZWFuaW5nIG9mIGFuIEF2ZXJhZ2UiLCJkZXNjcmlwdGlvbiI6IjxwPlRvIGFkdmVydGlzZSBoaXMgbmV3IGFydHdvcmssIEhlQnllIHBsYW5zIHRvIG1hbmlwdWxhdGUgaXRzIHN0YXIgcmF0aW5nIHJldmlld3MuIE9mIGNvdXJzZSwgc2ltcGx5IGdlbmVyYXRpbmcgbmV3IHJldmlld3MgaXMgZ29pbmcgdG8gcmFpc2Ugc3VzcGljaW9uLCBzbyBoZSBwbGFucyB0byBpbnN0ZWFkIG1hbmlwdWxhdGUgdGhlIHN0YXIgcmF0aW5ncyB1c2luZyB0aGUgbWVhbiB2YWx1ZSBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkZpcnN0LCBIZUJ5ZSBjb2xsZWN0cyB0aGUgJE4kIHN0YXIgcmF0aW5ncyBvbiBoaXMgYXJ0d29yayBpbiBhIGxpc3QuPFwvbGk+XHJcblx0PGxpPlRoZW4sIGhlIHJlcGVhdHMgdGhlIGZvbGxvd2luZyBwcm9jZWR1cmUgdW50aWwgdGhlcmUgaXMgb25seSAkMSQgc3RhciByYXRpbmcgcmVtYWluaW5nIGluIHRoZSBsaXN0LlxyXG5cdDx1bD5cclxuXHRcdDxsaT5TZWxlY3QgJDIkIG9yIG1vcmUgc3RhciByYXRpbmdzIGZyb20gdGhlIGxpc3QuPFwvbGk+XHJcblx0XHQ8bGk+RXJhc2UgdGhlIHNlbGVjdGVkIHJhdGluZ3MgZnJvbSB0aGUgbGlzdCwgYW5kIHRoZW4gYXBwZW5kIHRoZWlyIG1lYW4gdmFsdWUgdG8gdGhlIGxpc3QuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPlRoZSBsYXN0IHJlbWFpbmluZyBzdGFyIHJhdGluZyBpbiB0aGUgbGlzdCBiZWNvbWVzIHRoZSBuZXcgc3RhciByYXRpbmcgZm9yIHRoZSBhcnR3b3JrLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkZpbmQgdGhlIG1heGltdW0gc3RhciByYXRpbmcgSGVCeWUgY2FuIGFjaGlldmUgYnkgbWFuaXB1bGF0aW5nIGl0IGFzIGFib3ZlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiBzdGFyIHJhdGluZ3MgJE4kLiAkKDEgXFxsZSBOIFxcbGUgMjAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zICROJCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEFfMSwgQV8yLCBcXGxkb3RzLCBBX04kLCBkZW5vdGluZyB0aGUgc3RhciByYXRpbmdzLiAkKDAgXFxsZSBBX2kgXFxsZSAxMF45KSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbWF4aW11bSBzdGFyIHJhdGluZyBIZUJ5ZSBjYW4gYWNoaWV2ZSBpbiB0aGUgZmlyc3QgbGluZS48XC9wPlxyXG5cclxuPHA+WW91ciBhbnN3ZXIgaXMgY29uc2lkZXJlZCBjb3JyZWN0IGlmIGl0cyBhYnNvbHV0ZSBvciByZWxhdGl2ZSBlcnJvciBkb2VzbiZyc3F1bzt0IGV4Y2VlZCAkMTBeey05fSQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8cD5JZiB5b3Ugc2VsZWN0IGFsbCAkMyQgcmF0aW5ncyBhbmQgdGFrZSB0aGVpciBtZWFuIHZhbHVlLCB0aGUgc3RhciByYXRpbmcgZm9yIHRoZSBhcnR3b3JrIGlzICQyMCQuPFwvcD5cclxuXHJcbjxwPkhvd2V2ZXIsIGlmIHlvdSBmaXJzdCBzZWxlY3QgJDEwJCBhbmQgJDIwJCB0byBtYWtlICQxNSQsIGFuZCB0aGVuIHVzZSBpdCB3aXRoICQzMCQgdG8gdGFrZSB0aGUgbWVhbiB2YWx1ZSwgeW91IGNhbiBnZXQgJDIyLjUkLjxcL3A+XHJcbiJ9XQ==