Задача J. В ожидании открытия
Задачу добавил: alef
Успешно сдано решений: 9
Участники чемпионата, которые уже успели зарегистрироваться, в ожидании церемонии открытия играют в игру «Узнай персону» (да, возможно, Вы сталкивались с такой игрой на Акинаторе :-) ).
На листке бумаги записаны фамилии персон. На настоящий момент их осталось N.
Угадывающий может задавать любые вопросы, позволяющие ответить «да» или «нет». Конечно, вопросы могут быть совершенно абстрактные, например «Помогают ли корни уравнения x^2 + 1 = 0 зелюкам прятаться от Шалтая-Болтая?». Но, как правило, угадывающий стремится каждый раз сократить количество вариантов. Конечная цель — определить, какая персона загадана.
Для каждой из N персон известна вероятность того, что именно она является правильным ответом (при этом правильным ответом явлется ровно одна персона). Ваша задача — определить наименьшее в среднем количество вопросов, за которые можно узнать верный ответ.
Формат входного файла input.txt
Первая строка — целое число N (1 <= N <= 50) — количество персон
Вторая строка — N натуральных чисел через пробел, задающих вероятности того, что соответствующая персона является «правильной», в долях 0.0001. Сумма этих чисел составляет 10000.
Формат выходного файла output.txt
Первая строка — целое число — среднее число вопросов, которые требуется задать, чтобы узнать правильный ответ (также в долях 0.0001).
Пример входного файла — 1
4
1000 2000 3000 4000
Пример выходного файла — 1
19000
Пояснение к примеру.
Пусть осталось 4 персоны — это Павлов, Мечников, Сеченов и Фихтенгольц.
Вероятности, что это «правильная» персона для них (соответственно) таковы: 0.4, 0.3, 0.2 и 0.1
Как можно задавать вопросы?
Например, можно задать вопрос «Это Мечников или Сеченов или Фихтенгольц?» и получить ответ «да» или «нет». Если был дан ответ «да», то, конечно, это Павлов. Если же был дан ответ «нет», то далее можно спросить, допустим, «Это Мечников?» и, в случае отрицательного ответа, последним вопросом явно определить, кто это.
Тогда в среднем понадобится 0.4 * 1 + 0.3. * 2 + 0.2 * 3 + 0.1 *3 = 1.9 вопроса
Если же первым вопросом будет «Это Павлов или Фихтенгольц?», то в среднем получится 2 * (0.4 + 0.3 + 0.2 + 0.1) = 2.
Таким образом, первый путь ведет к меньшему числу.
Пример входного файла — 2
10
600 1000 500 800 1000 500 400 200 2000 3000
Пример выходного файла — 2
29600