ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование школьников. Октябрь 2005

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Курьер

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Фредди работает курьером у Вито Маретти. Однажды утром он получил задание доставить N контейнеров с виски — все в разные города штата. На доставку каждого контейнера из списка уйдет по одному дню. Но у каждого из заказов (один заказ — один контейнер) есть свой срок доставки и свое вознаграждение для Фредди. За просроченный заказ Фредди не получит нисколько денег, а может и нарваться на неприятности, так что доставлять такие контейнеры нет никакого смысла. Помогите ему составить график работы, который принесет максимальную прибыль, — Фредди в долгу не останется!

Исходные данные

Первая строка содержит число N, количество заказов (1 ≤ N ≤ 1000). В каждой из последующих N строк находится по два целых числа: срок доставки контейнера и размер вознаграждения. Срок доставки — от 1 до 100000 дней, премия — от 1 до 100000 долларов.

Результат

В первой строке должно быть количество контейнеров, которые доставит Фредди. Вторая строка должна содержать номера этих контейнеров через пробел в том порядке, в каком их нужно доставлять. Доставка просроченных заказов недопустима. Если решений несколько, выведите любое.

Пример

исходные данныерезультат
4
1 17
5 15
2 10
2 11
3
1 4 2
Автор задачи: Никита Рыбак
Источник задачи: XII командный чемпионат школьников Свердловской области по программированию (15 октября 2005 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1403. Курьер