Входной файл: tester.in Выходной файл: tester.out Время на тест: 2 секунды Авторы задачи: В.М. Котов, С.И. Кашкевич Тесты к задаче:Скачать
Девятиклассник Вася Пупкин, несмотря на свою молодость,
получил широкую известность как классный бета-тестер, и
поэтому он завален предложениями от различных программистских команд.
К сожалению, его молодость мешает ему правильно распределить свои силы и
отказаться от некоторых предложений, какими бы заманчивыми они не казались:
Ваша задача - помочь Васе определиться с выбором.
Итак, Васе предложено для тестирования N программ (1 <= N <= 1000). Он знает,
что для тестирования i-й программы (i=1, 2, ... , N) ему потребуется ti дней.
Кроме того, он не может работать над несколькими проектами одновременно,
и, закончив тестирование одной программы, приступает к работе над другой
не раньше следующего дня. Сегодня Вася отдыхает, ожидая Вашего решения:
С другой стороны, авторы программ ставят жесткие условия - работа над
i-й программой должна быть завершена через Di дней, начиная с сегодняшнего.
Например, если тестирование надо завершить послезавтра, то Di = 2.
Вы должны отвергнуть минимальное число предложений, чтобы не затянуть
сроки сдачи остальных проектов, а также составить для Васи одну из возможных
последовательностей выполнения оставшихся заказов.
Входные данные находятся в текстовом файле TESTER.IN и
состоят из нескольких строк. Первая строка содержит
десятичную запись числа N. Каждая из последующих N строк
содержит значения ti и Di (1 <= ti <= Di <= 1000), разделенные пробелами.
Выходные данные помещаются в текстовый файл TESTER.OUT. Первая строка
этого файла содержит число отвергнутых предложений. Последующие строки
содержат номера проектов (по одному в строке), которые Вася будет выполнять,
а порядок следования этих номеров соответствует порядку выполнения заказов.