| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 75 | 31 | 27 | 41.538% |
Vytautas Kalėdų proga gavo naują k'artą ir nori jį išbandyti ilgoje ir tiesioje kartingo trasoje.
Trasą kartas pradeda su pilnu kuro baku. Nuvažiuodamas vieną kilometrą kartas sunaudoja vieną litrą kuro. Kartas važiuoja tiesiai, kol bake yra kuro. Kuro baką galima pripildyti iki pilno bet kurioje degalų stotelėje.
Trasoje yra N stotelių, kurių i-toji stovi pi kilometrų nuo trasos pradžios.
Padėkite Vytautui apskaičiuoti, kokios mažiausios talpos kuro bako jam reikia, kad jam pavyktų nuvažiuoti bent K kilometrų.
Pirmojoje įvesties eilutėje pateikti du sveikieji teigiami skaičiai – stotelių skaičius N ir norimų nuvažiuoti kilometrų skaičius K.
Antrojoje įvesties eilutėje pateikta N sveikųjų teigiamų skaičių – i-tasis jų žymi i-tosios stotelės atstumą nuo trasos pradžios kilometrais. Stotelių pozicijas Vytautas gavo iš kelininkų, kurie jas pateikė kažkokia, tik jiems žinoma, tvarka – t. y. pozicijos nebūtinai bus išrikiuotos.
Išveskite vieną skaičių – minimalios bako talpos dydį litrais, su kuria Vytautui pavyktų nuvažiuoti bent K kilometrų.
5 50 25 5 28 48 40
20
Sakykime, kartas turi 19 litrų kuro baką. Pirmiausiai jis privažiuos stotelę ties 5-u kilometru – čia jis papildys savo baką nuo 14 iki 19 litrų. Toliau kartui jau nebepavyks pasiekti kitos stotelės, nes jo bakas ištuštės ties 24-u kilometru.
Turint 20 litrų kuro baką, kartui pavyks nuvažiuot 68 kilometrus. Kadangi 20 litrų yra mažiausia talpa, leidžianti nuvažiuoti bent 50 kilometrų, 20 yra sprendinys (1 pav.).
1 pav. Pavyzdys su 20 litrų baku