0182. Б-станция

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 s
Ограничение по памяти: 64 megabytes

Недалеко от Берляндии после землетрясения подводная станция оказалась частично затопленной. Она состоит из N уровней. Про каждый уровень известно Wi – количество воды на уровне до начала террористической операции, Li – количество воды, которое уровень способен выдержать и Pi – количество денег, необходимое террористам, чтобы повредить герметизацию уровня. Когда уровень разгерметизирован, вся вода с него переливается на следующий уровень. Если на уровне оказалось воды больше Li, то он разгерметизируется. Террористы Пивляндии хотят разгерметизировать последний уровень, затратив минимальное количество денег. Для этого они наняли вас.

Формат входного файла

В первой строке входного файла записано N (1 ≤ N ≤ 15000). Далее идет информация об уровнях: N строк с числами Wi, Li, Pi (0 ≤ Wi, Li, Pi ≤ 15000).

Формат выходного файла

В выходной файл нужно выдать номера уровней, которые следует разгерметизировать.

Пример:

input.txtoutput.txt
3 1000 1000 1 0 1000 2 2 10 100 1 2


Источник: Petrozavodsk Summer 2002. Saratov SU Contest, Tuesday, July 11

Обсудить       Отправить решение



Версия для печати