Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2353. Игра
Теория вероятностейОлимпиадные задачи на русском языке
| 14/10/2017 | Открытые личные соревнования по спортивному программированию (E) |
Ограничения: время – 500ms/1000ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
