|
Губернатор
(Время: 1 сек. Память: 16 Мб Сложность: 56%)
Вам, как губернатору города, необходимо организовать в своем городе постройку нескольких зданий, чтобы привести его в соответствие мировым стандартам. Губернатор вы не простой, а с высшим экономическим образованием, поэтому Вас в первую очередь заботит денежная сторона вопроса. Создав комиссию по этому поводу и проведя первое заседание, вы выяснили следующее.
В настоящее время, то есть до постройки требуемых зданий, город приносит стабильный доход – K золотых монет в месяц. Однако постройка любого здания может существенно изменить сложившееся положение.
Пронумеруем здания, требующие постройки числами от 1 до N, где N – их количество. Каждое здание i характеризуется двумя числами. Во-первых, это число ai – его эффективность. Она является вещественным числом и обозначает то, во сколько раз возрастет текущая прибыль при постройке этого здания. Второй параметр bi – это количество золотых монет, которые каждый месяц уходят на содержание этого здания. В итоге, если к моменту постройки i-го здания месячный доход составлял X монет, то после постройки этого здания его величина станет равна ai•X – bi. Отметим, что итоговый доход не обязательно будет целым числом.
Следует также учесть, что комитет по городскому строительству имеет сравнительно небольшой и мало обученный штат. Нехватка квалифицированных административных кадров проявляется прежде всего в том, что строители не могут работать над двумя проектами одновременно, а начав работу над одним зданием, не могут перейти к другому, не закончив первое.
Перед комиссией теперь стоит нелегкая задача: решить, в каком порядке строить здания – а строить их надо все, даже те, которые невыгодны – чтобы получать максимальный доход после постройки всех зданий. Как и следовало ожидать, для ваших коллег это оказалось слишком сложной задачей. Помогите им!
Входные данные
В первой строке входного файла INPUT.TXT записаны через пробел два целых числа N и K (1 ≤ N ≤ 10 000, 1 ≤ K ≤ 106). Далее, в каждой из N последующих строк описано по зданию. Каждое описание имеет вид ai bi, где число ai – вещественное (0 ≤ ai ≤ 10), а bi – целое (0 ≤ bi ≤ 100). i-ая из строк файла соответствует (i−1)-му зданию в нумерации, используемой комиссией.
Выходные данные
В выходной файл OUTPUT.TXT выведите перестановку из N чисел от 1 до N, по одному числу на строку – номера зданий в порядке их постройки. Если существует несколько перестановок, максимизирующих прибыль, разрешается вывести любую.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 10
1 5
2 3 | 2 1 |
2 | 4 6
1.2 3
1.5 2
2.0 4
0.5 1 | 2 3 1 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |