06/04/2025 12:00:30

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

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

Задачи

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

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

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

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

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

Задачи

78. Прибор

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

Прибор состоит из нескольких блоков. Для каждого блока известна вероятность его безотказной работы в течение определённого времени (надежность). Если хотя бы один из блоков прибора выходит из строя, перестаёт работать весь прибор, в связи с этим вероятность безотказной работы всего прибора

$P$ находится как произведение надёжностей его блоков:

$P\ =\ p_1⋅p_2⋅…⋅p_N$ . Для повышения надёжности прибора было принято решение выполнить резервирование некоторых блоков. Резервирование блока – это подключение параллельно к нему одного или нескольких таких же блоков. При аварии первого блока его функции будет выполнять второй, и т.д., на надёжность всех остальных блоков эта замена не повлияет. Будем считать, что вероятность безотказной работы группы из

$K$ одинаковых блоков (включая исходный) находится следующим образом:

$p'=1-(1-p)^K$ , где

$p$ – вероятность безотказной работы одного такого блока. Вероятность безотказной работы прибора тогда определится как

$P'\ =\ p'_1⋅p'_2·…⋅p'_N$ . Известна стоимость каждого блока и сумма

$S$ , выделенная на модернизацию всего прибора.

Требуется найти максимальную вероятность безотказной работы прибора, которую мы можем получить при условии, что суммарная стоимость добавленных блоков не должна превышать

$S$ .

В первой строке входного файла находится целое число

$N$ (

$1\ ≤\ N\ ≤\ 30$ ) – количество блоков в приборе. В следующих

$N$ строках через пробел записано по два числа – вероятность безотказной работы очередного блока

$p_i$ и его стоимость

$s_i$ (

$p_i$ – вещественное число,

$0\ <\ p_i\ ≤\ 1$ ,

$s_i$ – целое число,

$1\ ≤\ s_i\ ≤1000$ ). В следующей строке записано целое число

$S$ (

$0\ ≤\ S\ ≤\ 1000$ ) – сумма, выделенная на модернизацию прибора.

В первую строку выходного файла выведите одно число – вероятность безотказной работы прибора после модернизации с пятью десятичными цифрами после запятой.

Пример ввода

Пример вывода 2

0.62899

Источник: VII межвузовская олимпиада по программированию Вологда, 2004

03/07/2006	Лето 2006 дорешивание (11H)
28/07/2006	Лето 2006 - 11 (H)