print2353. Игра

printИгра

Ограничения: время – 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` – порядок прохождения уровней, при котором математическое ожидание суммарного количества баллов является максимальным. Если существует несколько вариантов, максимизирующих математическое ожидание, то можно вывести любой из них.

Пример ввода

3
1 10
50 1
20 1

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

2 3 1

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

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