시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 63 35 22 56.410%

문제

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

쿠키런을 즐겨 플레이하는 샤바칸은 매일같이 하트가 충전되기를 기다리던 중, 한 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+XHVjODA0XHVjMTI0IFx1Y2U3NFx1YjRkYzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzVmNFx1YzJlY1x1ZDc4OCBcdWFjZThcdWI0ZGNcdWI5N2MgXHViYWE4XHVjNzQwIFx1YzBlNFx1YmMxNFx1Y2U3OFx1Yzc0MCBOXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFkNmNcdWM3ODVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwZTRcdWJjMTRcdWNlNzhcdWM3NDAgXHVhZDZjXHVjNzg1XHVkNTVjIFx1YWMwMSBOXHVjN2E1XHVjNzU4IFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWI0ZjFcdWFlMDlcdWM3NDQgXHVkNTU4XHViMDk4XHVjNzU4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IDReTlx1YWMwMFx1YzljMFx1Yzc1OCBcdWI0ZjFcdWFlMDkgXHVjMjFjXHVjNWY0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWFjMDFcdWFjMDEgXHViMzAwXHVjNzUxXHViNDE4XHViMjk0IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YjA1ZFx1Yzc0NCBcdWJhODVcdWQ2NTVcdWQ3ODggXHVjNTRjIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVjNzc0XHViNGU0IFx1YzkxMSBcdWM1YjRcdWI1YTBcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHViM2M0IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjODExXHViNDUwXHVjMGFjKHByZWZpeClcdWFjMDAgXHViNDE4XHVjNWI0XHVjMTFjXHViMjk0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZDZjXHVjNzg1XHVkNTVjIFx1Y2U3NFx1YjRkY1x1YzVkMFx1YzExYyBcdWJjMWNcdWMwZGRcdWQ1NThcdWIyOTQgXHViNGYxXHVhZTA5XHVjNzU4IFx1ZDY1NVx1Yjk2MFx1YmQ4NFx1ZDNlY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWM1YjRcdWI1YTBcdWQ1NWMgTlx1YzdhNVx1Yzc1OCBcdWI0ZjFcdWFlMDkgXHVjMjFjXHVjNWY0XHVjNWQwXHVjMTFjIFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViY2MwXHVkNjU4XHVkNTU4XHViMjk0IFx1ZDQ1Y1x1ZDYwNCBcdWJjMjlcdWJjOTVcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjMGU0XHViYzE0XHVjZTc4XHVjNzc0IFx1YWMwMSBcdWM3NzRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDQgXHVhZDZjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWQxYjVcdWQ1NzQgXHVjNmIwXHViOWFjXHViMjk0IFx1YzBlNFx1YmMxNFx1Y2U3OFx1Yzc3NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjNzc0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVhZTMwXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkNmNcdWM3ODVcdWQ1NWMgXHVjZTc0XHViNGRjXHVjNWQwXHVjMTFjIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YjI5NCBcdWI0ZjFcdWFlMDlcdWM3NTggXHVkNjU1XHViOTYwXHViZDg0XHVkM2VjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YzBlNFx1YmMxNFx1Y2U3OFx1Yzc3NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjNzc0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVhZTMwXHViMzEzXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFkNmNcdWM3ODVcdWQ1NThcdWIyOTQgXHVjZTc0XHViNGRjXHVjNzU4IFx1YzIxOCBOICgxICZsZTsgTiAmbGU7IDIwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWQ2Y1x1Yzc4NVx1ZDU1YyBcdWNlNzRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHViYzFjXHVjMGRkXHVkNTU4XHViMjk0IFx1Yzc3Y1x1YmMxOCBcdWNlNzRcdWI0ZGMsIFx1ZDc2Y1x1YWRjMCBcdWNlNzRcdWI0ZGMsIFx1YzYwMVx1YzZjNSBcdWNlNzRcdWI0ZGMsIFx1YzgwNFx1YzEyNCBcdWNlNzRcdWI0ZGNcdWM3NTggXHVkNjU1XHViOTYwIFx1YmQ4NFx1ZDNlYyBQPHN1Yj5DPFwvc3ViPiwgUDxzdWI+UjxcL3N1Yj4sIFA8c3ViPkU8XC9zdWI+LCBQPHN1Yj5MPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBQPHN1Yj5DPFwvc3ViPitQPHN1Yj5SPFwvc3ViPitQPHN1Yj5FPFwvc3ViPitQPHN1Yj5MPFwvc3ViPj0xXHVjNzg0XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQxY1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwZTRcdWJjMTRcdWNlNzhcdWM3NzQgXHVjMGFjXHVjNmE5XHVkNTYwIFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1YWUzMFx1YjMxM1x1YWMxMlx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MDhcdWIzMDAgXHViNjEwXHViMjk0IFx1YzBjMVx1YjMwMCBcdWM2MjRcdWNjMjhcdWFjMDAgMTA8c3VwPi00PFwvc3VwPlx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWFjYmRcdWM2YjAgXHVjODE1XHViMmY1XHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxNVx1YjQxY1x1YjJlNDxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwOTgzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2VhdGhlciBSZXBvcnQiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBoYXZlIGJlZW4gaGlyZWQgYnkgdGhlIEFzc29jaWF0aW9uIGZvciBDbGltYXRvbG9naWNhbCBNZWFzdXJlbWVudCwgYSBzY2llbnRpZmljIG9yZ2FuaXphdGlvbiBpbnRlcmVzdGVkIGluIHRyYWNraW5nIGdsb2JhbCB3ZWF0aGVyIHRyZW5kcyBvdmVyIGEgbG9uZyBwZXJpb2Qgb2YgdGltZS4gT2YgY291cnNlLCB0aGlzIGlzIG5vIGVhc3kgdGFzay4gVGhleSBoYXZlIGRlcGxveWVkIG1hbnkgc21hbGwgZGV2aWNlcyBhcm91bmQgdGhlIHdvcmxkLCBkZXNpZ25lZCB0byB0YWtlIHBlcmlvZGljIG1lYXN1cmVtZW50cyBvZiB0aGUgbG9jYWwgd2VhdGhlciBjb25kaXRpb25zLiBUaGVzZSBhcmUgY2hlYXAgZGV2aWNlcyB3aXRoIHNvbWV3aGF0IHJlc3RyaWN0ZWQgY2FwYWJpbGl0aWVzLiBFdmVyeSBkYXkgdGhleSBvYnNlcnZlIHdoaWNoIG9mIHRoZSBmb3VyIHN0YW5kYXJkIGtpbmRzIG9mIHdlYXRoZXIgb2NjdXJyZWQ6IFN1bm55LCBDbG91ZHksIFJhaW55LCBvciBGcm9ncy4gQWZ0ZXIgZXZlcnkgbiBvZiB0aGVzZSBvYnNlcnZhdGlvbnMgaGF2ZSBiZWVuIG1hZGUsIHRoZSByZXN1bHRzIGFyZSByZXBvcnRlZCB0byB0aGUgbWFpbiBzZXJ2ZXIgZm9yIGFuYWx5c2lzLiBIb3dldmVyLCB0aGUgbWFzc2l2ZSBudW1iZXIgb2YgZGV2aWNlcyBoYXMgY2F1c2VkIHRoZSBhdmFpbGFibGUgY29tbXVuaWNhdGlvbiBiYW5kd2lkdGggdG8gYmUgb3ZlcmxvYWRlZC4gVGhlIEFzc29jaWF0aW9uIG5lZWRzIHlvdXIgaGVscCB0byBjb21lIHVwIHdpdGggYSBtZXRob2Qgb2YgY29tcHJlc3NpbmcgdGhlc2UgcmVwb3J0cyBpbnRvIGZld2VyIGJpdHMuPFwvcD5cclxuXHJcbjxwPkZvciBhIHBhcnRpY3VsYXIgZGV2aWNlJnJzcXVvO3MgbG9jYXRpb24sIHlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIHdlYXRoZXIgZWFjaCBkYXkgaXMgYW4gaW5kZXBlbmRlbnQgcmFuZG9tIGV2ZW50LCBhbmQgeW91IGFyZSBnaXZlbiB0aGUgcHJlZGljdGVkIHByb2JhYmlsaXRpZXMgb2YgdGhlIGZvdXIgcG9zc2libGUgd2VhdGhlciB0eXBlcy4gRWFjaCBvZiB0aGUgNDxzdXA+bjxcL3N1cD4mbmJzcDtwb3NzaWJsZSB3ZWF0aGVyIHJlcG9ydHMgZm9yIGEgZGV2aWNlIG11c3QgYmUgZW5jb2RlZCBhcyBhIHVuaXF1ZSBzZXF1ZW5jZSBvZiBiaXRzLCBzdWNoIHRoYXQgbm8gc2VxdWVuY2UgaXMgYSBwcmVmaXggb2YgYW55IG90aGVyIHNlcXVlbmNlIChhbiBpbXBvcnRhbnQgcHJvcGVydHksIG9yIGVsc2UgdGhlIHNlcnZlciB3b3VsZCBub3Qga25vdyB3aGVuIGVhY2ggc2VxdWVuY2UgZW5kcykuIFRoZSBnb2FsIGlzIHRvIHVzZSBhbiBlbmNvZGluZyB0aGF0IG1pbmltaXplcyB0aGUgZXhwZWN0ZWQgbnVtYmVyIG9mIHRyYW5zbWl0dGVkIGJpdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIDEgJmxlOyBuICZsZTsgMjAsIHRoZSBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zIHRoYXQgZ28gaW50byBlYWNoIHJlcG9ydC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGZvdXIgcG9zaXRpdmUgZmxvYXRpbmctcG9pbnQgbnVtYmVycywgcDxzdWI+c3Vubnk8XC9zdWI+LCBwPHN1Yj5jbG91ZHk8XC9zdWI+LCBwPHN1Yj5yYWlueTxcL3N1Yj4sIGFuZCBwZnJvZ3MsIHJlcHJlc2VudGluZyB0aGUgcmVzcGVjdGl2ZSB3ZWF0aGVyIHByb2JhYmlsaXRpZXMuIFRoZXNlIHByb2JhYmlsaXRpZXMgaGF2ZSBhdCBtb3N0IDYgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50IGFuZCBzdW0gdG8gMS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5EaXNwbGF5IHRoZSBtaW5pbXVtIGV4cGVjdGVkIG51bWJlciBvZiBiaXRzIGluIHRoZSBlbmNvZGluZyBvZiBhIHJlcG9ydCwgd2l0aCBhbiBhYnNvbHV0ZSBvciByZWxhdGl2ZSBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4mbWludXM7NDxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d