Подразделы

Другие разделы

Дата и время

05/04/2025 18:59:47

Авторизация

2353. Игра

Игра

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

Петя проходит видеоигру, в которой нет возможности сохранения. В игре

$N$ уровней, которые можно проходить в любом порядке. Каждый уровень можно проходить только один раз. За успешное прохождение

$i$ -го уровня начисляется

$B_i$ баллов. Если Петя не может пройти уровень, то игра заканчивается. Петя знает вероятность

$P_i$ успешного прохождения каждого уровня.

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

Первая строка ввода содержит

$N$ (

$2\ ≤\ N\ ≤\ 100$ ) – количество уровней. Далее следует

$N$ строк, в каждой строке два целых числа – вероятность успешного прохождения уровня

$P_i$ в процентах (

$1\ ≤\ P_i\ ≤\ 100$ ) и начисляемые за уровень баллы

$B_i$ (

$1\ ≤\ B_i\ ≤\ 1000$ ).

Вывести

$N$ целых чисел в диапазоне от 1 до

$N$ – порядок прохождения уровней, при котором математическое ожидание суммарного количества баллов является максимальным. Если существует несколько вариантов, максимизирующих математическое ожидание, то можно вывести любой из них.

Пример ввода

Вывод для примера

2 3 1

Разбор задачи E. Игра

Математическое ожидание суммы баллов равно