시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB67393063.830%

문제

“영웅이여, 대 마상시합에 온 것을 환영합니다!” – 심판관 트루하트

쿠키런을 즐겨 플레이하는 샤바칸은 매일같이 하트가 충전되기를 기다리던 중, 한 TCG 장르의 게임을 접한다. 이 게임은 양 플레이어가 자신이 가진 카드 중 가장 좋은 30장을 순서대로 늘어놓아 자랑하며 경쟁하고, 여기서 번 골드를 이용해 새로운 카드를 구매하는 컨텐츠로 이루어져 있는데, 구입하는 새로운 카드는 무작위로 나타난다. 존재하는 카드의 등급은 다음과 같다.

  • 일반 카드
  • 희귀 카드
  • 영웅 카드
  • 전설 카드

열심히 골드를 모은 샤바칸은 N장의 카드를 구입하려고 한다. 샤바칸은 구입한 각 N장의 카드의 등급을 하나의 이진 문자열로 표현하고자 한다. 즉, 서로 다른 4^N가지의 등급 순열에 대해 각각 대응되는 이진 문자열이 존재해야 하며, 문자열의 끝을 명확히 알 수 있도록 이들 중 어떠한 문자열도 다른 문자열의 접두사(prefix)가 되어서는 안 된다.

구입한 카드에서 발생하는 등급의 확률분포가 주어질 때, 어떠한 N장의 등급 순열에서 이진 문자열로 변환하는 표현 방법에 대해, 우리는 샤바칸이 각 이진 문자열을 사용할 확률을 구할 수 있다. 이를 통해 우리는 샤바칸이 사용할 이진 문자열의 길이의 기댓값을 구할 수 있다.

구입한 카드에서 발생하는 등급의 확률분포가 주어질 때, 샤바칸이 사용할 이진 문자열의 길이의 기댓값의 최솟값을 구하시오. 

입력

입력의 첫 줄에는 구입하는 카드의 수 N (1 ≤ N ≤ 20)이 주어진다.

입력의 둘째 줄에는 구입한 카드에서 발생하는 일반 카드, 희귀 카드, 영웅 카드, 전설 카드의 확률 분포 PC, PR, PE, PL가 주어진다. 여기서 PC+PR+PE+PL=1임이 보장된다. 

출력

출력의 첫 줄에는 샤바칸이 사용할 이진 문자열의 길이의 기댓값의 최솟값을 출력한다.

절대 또는 상대 오차가 10-4이하인 경우 정답으로 인정된다

예제 입력 1

2
0.9 0.049999 0.05 0.000001

예제 출력 1

1.457510

예제 입력 2

20
0.25 0.25 0.25 0.25

예제 출력 2

40.000000
W3sicHJvYmxlbV9pZCI6IjEwOTgzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNzg4XHVhZTMwXHVjZTc0XHViNGRjIiwiZGVzY3JpcHRpb24iOiI8cD4mbGRxdW87XHVjNjAxXHVjNmM1XHVjNzc0XHVjNWVjLCBcdWIzMDAgXHViOWM4XHVjMGMxXHVjMmRjXHVkNTY5XHVjNWQwIFx1YzYyOCBcdWFjODNcdWM3NDQgXHVkNjU4XHVjNjAxXHVkNTY5XHViMmM4XHViMmU0ISZyZHF1bzsgJm5kYXNoOyBcdWMyZWNcdWQzMTBcdWFkMDAgXHVkMmI4XHViOGU4XHVkNTU4XHVkMmI4PFwvcD5cclxuXHJcbjxwPlx1Y2ZlMFx1ZDBhNFx1YjdmMFx1Yzc0NCBcdWM5OTBcdWFjYTggXHVkNTBjXHViODA4XHVjNzc0XHVkNTU4XHViMjk0IFx1YzBlNFx1YmMxNFx1Y2U3OFx1Yzc0MCBcdWI5ZTRcdWM3N2NcdWFjMTlcdWM3NzQgXHVkNTU4XHVkMmI4XHVhYzAwIFx1Y2RhOVx1YzgwNFx1YjQxOFx1YWUzMFx1Yjk3YyBcdWFlMzBcdWIyZTRcdWI5YWNcdWIzNTggXHVjOTExLCBcdWQ1NWMgVENHIFx1YzdhNVx1Yjk3NFx1Yzc1OCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjODExXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YzU5MSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YWMwMFx1YzljNCBcdWNlNzRcdWI0ZGMgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgMzBcdWM3YTVcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YjI5OFx1YzViNFx1YjE5M1x1YzU0NCBcdWM3OTBcdWI3OTFcdWQ1NThcdWJhNzAgXHVhY2JkXHVjN2MxXHVkNTU4XHVhY2UwLCBcdWM1ZWNcdWFlMzBcdWMxMWMgXHViYzg4IFx1YWNlOFx1YjRkY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjMGM4XHViODVjXHVjNmI0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFkNmNcdWI5ZTRcdWQ1NThcdWIyOTQgXHVjZWU4XHVkMTUwXHVjZTIwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YWQ2Y1x1Yzc4NVx1ZDU1OFx1YjI5NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjZTc0XHViNGRjXHViMjk0IFx1YmIzNFx1Yzc5MVx1YzcwNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWM3NTggXHViNGYxXHVhZTA5XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzdjXHViYzE4IFx1Y2U3NFx1YjRkYzxcL2xpPlxyXG5cdDxsaT5cdWQ3NmNcdWFkYzAgXHVjZTc0XHViNGRjPFwvbGk+XHJcblx0PGxpPlx1YzYwMVx1YzZjNSBcdWNlNzRcdWI0ZGM8XC9saT5cclxuXHQ8bGk+XHVjODA0XHVjMTI0IFx1Y2U3NFx1YjRkYzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzVmNFx1YzJlY1x1ZDc4OCBcdWFjZThcdWI0ZGNcdWI5N2MgXHViYWE4XHVjNzQwIFx1YzBlNFx1YmMxNFx1Y2U3OFx1Yzc0MCBOXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFkNmNcdWM3ODVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwZTRcdWJjMTRcdWNlNzhcdWM3NDAgXHVhZDZjXHVjNzg1XHVkNTVjIFx1YWMwMSBOXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWI0ZjFcdWFlMDlcdWM3NDQgXHVkNTU4XHViMDk4XHVjNzU4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IDReTlx1YWMwMFx1YzljMFx1Yzc1OCBcdWI0ZjFcdWFlMDkgXHVjMjFjXHVjNWY0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFjMDFcdWFjMDEgXHViMzAwXHVjNzUxXHViNDE4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YjA1ZFx1Yzc0NCBcdWJhODVcdWQ2NTVcdWQ3ODggXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVjNzc0XHViNGU0IFx1YzkxMSBcdWM1YjRcdWI1YTBcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHViM2M0IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjODExXHViNDUwXHVjMGFjKHByZWZpeClcdWFjMDAgXHViNDE4XHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWQ2Y1x1Yzc4NVx1ZDU1YyBcdWNlNzRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViYzFjXHVjMGRkXHVkNTU4XHViMjk0IFx1YjRmMVx1YWUwOVx1Yzc1OCBcdWQ2NTVcdWI5NjBcdWJkODRcdWQzZWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVjNWI0XHViNWEwXHVkNTVjIE5cdWM3YTVcdWM3NTggXHViNGYxXHVhZTA5IFx1YzIxY1x1YzVmNFx1YzVkMFx1YzExYyBcdWM3NzRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YmNjMFx1ZDY1OFx1ZDU1OFx1YjI5NCBcdWQ0NWNcdWQ2MDQgXHViYzI5XHViYzk1XHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjNmIwXHViOWFjXHViMjk0IFx1YzBlNFx1YmMxNFx1Y2U3OFx1Yzc3NCBcdWFjMDEgXHVjNzc0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVkNjU1XHViOTYwXHVjNzQ0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI5N2MgXHVkMWI1XHVkNTc0IFx1YzZiMFx1YjlhY1x1YjI5NCBcdWMwZTRcdWJjMTRcdWNlNzhcdWM3NzQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1YWUzMFx1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVjNzg1XHVkNTVjIFx1Y2U3NFx1YjRkY1x1YzVkMFx1YzExYyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHViNGYxXHVhZTA5XHVjNzU4IFx1ZDY1NVx1Yjk2MFx1YmQ4NFx1ZDNlY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWMwZTRcdWJjMTRcdWNlNzhcdWM3NzQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1YWUzMFx1YjMxM1x1YWMxMlx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZDZjXHVjNzg1XHVkNTU4XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAyMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNmNcdWM3ODVcdWQ1NWMgXHVjZTc0XHViNGRjXHVjNWQwXHVjMTFjIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YjI5NCBcdWM3N2NcdWJjMTggXHVjZTc0XHViNGRjLCBcdWQ3NmNcdWFkYzAgXHVjZTc0XHViNGRjLCBcdWM2MDFcdWM2YzUgXHVjZTc0XHViNGRjLCBcdWM4MDRcdWMxMjQgXHVjZTc0XHViNGRjXHVjNzU4IFx1ZDY1NVx1Yjk2MCBcdWJkODRcdWQzZWMgUDxzdWI+QzxcL3N1Yj4sIFA8c3ViPlI8XC9zdWI+LCBQPHN1Yj5FPFwvc3ViPiwgUDxzdWI+TDxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgUDxzdWI+QzxcL3N1Yj4rUDxzdWI+UjxcL3N1Yj4rUDxzdWI+RTxcL3N1Yj4rUDxzdWI+TDxcL3N1Yj49MVx1Yzc4NFx1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGU0XHViYzE0XHVjZTc4XHVjNzc0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWM3NzRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWFlMzBcdWIzMTNcdWFjMTJcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODA4XHViMzAwIFx1YjYxMFx1YjI5NCBcdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHVhYzAwIDEwPHN1cD4tNDxcL3N1cD5cdWM3NzRcdWQ1NThcdWM3NzggXHVhY2JkXHVjNmIwIFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTVcdWI0MWNcdWIyZTQ8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDk4MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldlYXRoZXIgUmVwb3J0IiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgaGF2ZSBiZWVuIGhpcmVkIGJ5IHRoZSBBc3NvY2lhdGlvbiBmb3IgQ2xpbWF0b2xvZ2ljYWwgTWVhc3VyZW1lbnQsIGEgc2NpZW50aWZpYyBvcmdhbml6YXRpb24gaW50ZXJlc3RlZCBpbiB0cmFja2luZyBnbG9iYWwgd2VhdGhlciB0cmVuZHMgb3ZlciBhIGxvbmcgcGVyaW9kIG9mIHRpbWUuIE9mIGNvdXJzZSwgdGhpcyBpcyBubyBlYXN5IHRhc2suIFRoZXkgaGF2ZSBkZXBsb3llZCBtYW55IHNtYWxsIGRldmljZXMgYXJvdW5kIHRoZSB3b3JsZCwgZGVzaWduZWQgdG8gdGFrZSBwZXJpb2RpYyBtZWFzdXJlbWVudHMgb2YgdGhlIGxvY2FsIHdlYXRoZXIgY29uZGl0aW9ucy4gVGhlc2UgYXJlIGNoZWFwIGRldmljZXMgd2l0aCBzb21ld2hhdCByZXN0cmljdGVkIGNhcGFiaWxpdGllcy4gRXZlcnkgZGF5IHRoZXkgb2JzZXJ2ZSB3aGljaCBvZiB0aGUgZm91ciBzdGFuZGFyZCBraW5kcyBvZiB3ZWF0aGVyIG9jY3VycmVkOiBTdW5ueSwgQ2xvdWR5LCBSYWlueSwgb3IgRnJvZ3MuIEFmdGVyIGV2ZXJ5IG4gb2YgdGhlc2Ugb2JzZXJ2YXRpb25zIGhhdmUgYmVlbiBtYWRlLCB0aGUgcmVzdWx0cyBhcmUgcmVwb3J0ZWQgdG8gdGhlIG1haW4gc2VydmVyIGZvciBhbmFseXNpcy4gSG93ZXZlciwgdGhlIG1hc3NpdmUgbnVtYmVyIG9mIGRldmljZXMgaGFzIGNhdXNlZCB0aGUgYXZhaWxhYmxlIGNvbW11bmljYXRpb24gYmFuZHdpZHRoIHRvIGJlIG92ZXJsb2FkZWQuIFRoZSBBc3NvY2lhdGlvbiBuZWVkcyB5b3VyIGhlbHAgdG8gY29tZSB1cCB3aXRoIGEgbWV0aG9kIG9mIGNvbXByZXNzaW5nIHRoZXNlIHJlcG9ydHMgaW50byBmZXdlciBiaXRzLjxcL3A+XHJcblxyXG48cD5Gb3IgYSBwYXJ0aWN1bGFyIGRldmljZSZyc3F1bztzIGxvY2F0aW9uLCB5b3UgbWF5IGFzc3VtZSB0aGF0IHRoZSB3ZWF0aGVyIGVhY2ggZGF5IGlzIGFuIGluZGVwZW5kZW50IHJhbmRvbSBldmVudCwgYW5kIHlvdSBhcmUgZ2l2ZW4gdGhlIHByZWRpY3RlZCBwcm9iYWJpbGl0aWVzIG9mIHRoZSBmb3VyIHBvc3NpYmxlIHdlYXRoZXIgdHlwZXMuIEVhY2ggb2YgdGhlIDQ8c3VwPm48XC9zdXA+Jm5ic3A7cG9zc2libGUgd2VhdGhlciByZXBvcnRzIGZvciBhIGRldmljZSBtdXN0IGJlIGVuY29kZWQgYXMgYSB1bmlxdWUgc2VxdWVuY2Ugb2YgYml0cywgc3VjaCB0aGF0IG5vIHNlcXVlbmNlIGlzIGEgcHJlZml4IG9mIGFueSBvdGhlciBzZXF1ZW5jZSAoYW4gaW1wb3J0YW50IHByb3BlcnR5LCBvciBlbHNlIHRoZSBzZXJ2ZXIgd291bGQgbm90IGtub3cgd2hlbiBlYWNoIHNlcXVlbmNlIGVuZHMpLiBUaGUgZ29hbCBpcyB0byB1c2UgYW4gZW5jb2RpbmcgdGhhdCBtaW5pbWl6ZXMgdGhlIGV4cGVjdGVkIG51bWJlciBvZiB0cmFuc21pdHRlZCBiaXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciAxICZsZTsgbiAmbGU7IDIwLCB0aGUgbnVtYmVyIG9mIG9ic2VydmF0aW9ucyB0aGF0IGdvIGludG8gZWFjaCByZXBvcnQuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBmb3VyIHBvc2l0aXZlIGZsb2F0aW5nLXBvaW50IG51bWJlcnMsIHA8c3ViPnN1bm55PFwvc3ViPiwgcDxzdWI+Y2xvdWR5PFwvc3ViPiwgcDxzdWI+cmFpbnk8XC9zdWI+LCBhbmQgcGZyb2dzLCByZXByZXNlbnRpbmcgdGhlIHJlc3BlY3RpdmUgd2VhdGhlciBwcm9iYWJpbGl0aWVzLiBUaGVzZSBwcm9iYWJpbGl0aWVzIGhhdmUgYXQgbW9zdCA2IGRpZ2l0cyBhZnRlciB0aGUgZGVjaW1hbCBwb2ludCBhbmQgc3VtIHRvIDEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RGlzcGxheSB0aGUgbWluaW11bSBleHBlY3RlZCBudW1iZXIgb2YgYml0cyBpbiB0aGUgZW5jb2Rpbmcgb2YgYSByZXBvcnQsIHdpdGggYW4gYWJzb2x1dGUgb3IgcmVsYXRpdmUgZXJyb3Igb2YgYXQgbW9zdCAxMDxzdXA+Jm1pbnVzOzQ8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=