23/11/2024 15:21:55

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2640. Кто хочет стать миллионером?

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В игре "Кто хочет стать миллионером?" игрок должен ответить на `n` вопросов.
Приз удваивается в каждом раунде, но сложность вопросов также возрастает. После ответа на `n`-й вопрос игра завершается.
В данном варианте игры у игрока до начала 1-го раунда уже есть приз 1$.

Обычно после прочтения вопроса игрок может выбрать одно из действий:

* забрать уже выигранный приз и завершить игру;
* ответить на вопрос, удвоить свой приз при правильном ответе и продолжить играть, или уйти ни с чем при неправильном ответе.

Игрок может оценить вероятность `p_i` правильного ответа на `i`-й вопрос.

Первая строка ввода содержит одно целое число `N` (`1 <= N <= 30`) -- количество вопросов в игре.
Вторая строка ввода содержит `N` чисел `p_i` в диапазоне от 0 до 1 -- вероятность, что игрок может ответить правильно
на `i`-й вопрос.

Вывести одно число -- ожидаемый выигрыш игрока с точностью `10^{-3}` при наилучшей стратегии игрока.

```sample Пример ввода 1
1
0.6
```

```sample Пример вывода 1
1.200
```

```sample Пример ввода 2
3
1.0 0.3 0.9
```

```sample Пример вывода 2
2.160
```

Пояснение к примеру 1: Если игрок отвечает на вопрос правильно, то с вероятностью 0.6 он получает приз 2$, но с вероятностью 0.4 он теряет всё.
Таким образом ожидаемый выигрыш игрока равен `0.6*2+0.4*0=1.2`. При выборе варианта "забрать приз" он получит 1$, поэтому
лучшей стратегией будет попытаться ответить на вопрос.

02/10/2022	Очный тур личного первенства по спортивному программированию (H)
23/02/2023	Базовый уровень: динамическое программирование 1 (проводит BOGAT) (D)
06/03/2023	Игры 1 (проводит BOGAT) (D)
27/02/2024	Динамическое программирование 1 (проводит BOGAT) (D)