0182. Б-станция

Input file name: input.txt
Output file name: output.txt
Time limit: 1 s
Memory limit: 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


Source: Petrozavodsk Summer 2002. Saratov SU Contest, Tuesday, July 11

Discuss       Submit a solution



Printable version