Zadanie

Ako ste iste pochopili, KSP oslavuje 40. narodeniny, takže sa bude konať veľká oslava.

Oslava sa koná na Kikinej chate, kam sa ale všetci vedúci musia najprv dostať. Keďže ceny paliva sú stále vysoké, vedúci sa rozhodli, že si spravia turistiku.

Vybrali sa teda cez hory, kde na nich čakalo množstvo prekážok - strmých skál. Po skale sa nedá vyliezť, lebo je veľmi šmykľavá a nedá sa ju ani obísť.

Vedúci sú natrénovaní, a tak každý z nich dokáže vyskočiť do výšky \(k\) metrov.

Ak je skala vyššia ako \(k\) metrov, tak ju samostatne vedúci nepreskočí, ale dokážu si vzájomne pomôcť tak, že sa jeden druhému postavia na ramená, a tak vytvoria akýsi ľudský rebrík, po ktorom môže iný vedúci vyliezť. Každý vedúci má výšku \(1\) meter. Každý vedúci, ktorý sa stane rebríkom, sa musí obetovať a pod danou skalou ostať - nemôže pokračovať ďalej.

Kika už čaká na chate a chystá sa krájať tortu. Rada by ale vedela, koľko porcií má nachystať. Zistite, koľko vedúcich prejde pohorím a dorazí na chatu.

Úloha

Vašou úlohou bude zistiť, koľko najviac vedúcich z celkového počtu \(v\) dokáže prejsť pohorím a dorazí na chatu.

Na to aby vedúci mohol prejsť cez skalu potrebuje vedieť vyskočiť dostatočne vysoko. Ak je skala vyššia ako výška jeho skoku \(k\), požiada svojich spoluvedúcich o pomoc. Vedúci, ktorí tvorili ľudský rebrík sa musia obetovať a na chatu nikdy nedorazia.

Skaly, ktoré treba prekonať si môžete predstaviť ako postupnosť výšok skál zľava doprava, pričom vedúci vyrážajú úplne zľava, na nulovej výške a chata sa nachádza úplne vpravo, tiež v nulovej výške. Keď vedúci preskočí skalu, znova bude v nulovej výške (teda za každou skalou je zase chodník nulovej výšky).

Formát vstupu

V prvom riadku sú čísla \(n, v, k\) udávajúce počet skál, počet vedúcich a výšku skoku vedúceho.

V druhom riadku nasleduje \(n\) čísel, reprezentujúcich výšky jednotlivých skál.

Môžete predpokladať, že výška skaly nepresiahne číslo \(m\).

Sú 4 sady vstupov, a môžete v nich predpokladať nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq n \leq\) \(10\) \(10^3\) \(10^5\) \(10^5\)
\(1 \leq v \leq\) \(10\) \(10^3\) \(10^6\) \(10^{11}\)
\(1 \leq k \leq\) \(10\) \(10^3\) \(10^6\) \(10^9\)
\(1 \leq m \leq\) \(10\) \(10^3\) \(10^6\) \(10^9\)

Všimnite si, že v poslednej sade sa Vám vstupné premenné nemusia zmesiť do int-u, odporúčame preto v C/C++ použiť long.

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo udávajúce počet vedúcich, ktorým sa podarilo doraziť na chatu.

Príklady

Input:

5 20 10
5 7 3 4 2

Output:

20

Ani jedna skala nie je vyššia ako výška do ktorej vie vedúci doskočíť, čiže na chatu dorazí všetkých 20 vedúcich.

Input:

3 5 5
4 7 3

Output:

3

Prvú skalu sa podarilo zdolať všetkým, na druhej dvaja vedúci museli vytvoriť rebrík aby ostatní prešli, tretiu skalu zvyšni vedúci preskočili všetci.

Input:

3 7 2
14 1 2

Output:

0

Cez prvú skalu sa nedostal ani jeden vedúci, na chatu dorazilo 0 vedúcich.

Myšlienka riešenia

Aby sme zistili, koľko vedúcich sa dostane na chatu, potrebujeme najskôr zistiť počet vedúcich, ktorí budú pri každej skale tvoriť ľudský rebrík. To docielime tak, že od výšky skaly odčítame výšku skoku vedúceho, čo nam dá počet, koľko vedúcich je potrebné obetovať na ľudský rebrík. Ak je počet záporné číslo, znamená to, že vedúci vie preskočit danú skalu, a teda nebolo treba obetovať žiadneho vedúceho.

Po zistení počtu vedúcich, ktorí tvoria ľudský rebrík, odčítame dané číslo od celkového počtu vedúcich. (Vedúci, ktorí tvoria ľudský rebrík už ďalej ísť nemôžu)

Túto úvahu aplikujeme pre každú skalu na vstupe.

Ukážeme si myšlienku na \(2.\) príklade zo zadania:

Input:

3 5 5
4 7 3

Output:

3

Počet skál \(3\), výška skoku \(5\), počet vedúcich \(5\).

Skala výšky \(4 \to 4 - 5 = -1\), zoberieme max(-1, 0), teda \(5 - 0 = 5\), všetci vedúci prejdu.
Skala výšky \(7 \to 7 - 5 = 2\), zoberieme max(2, 0), teda \(5 - 2 = 3\), dvaja vedúci tvoria rebrík, zvyšní traja prejdu.
Skala výšky \(3 \to 3 - 5 = -2\), zoberieme max(-2, 0), teda \(3 - 0 = 3\), traja vedúci sa dostali na chatu.

Optimálne riešenie

Optimálne riešenie číta výšky skál a hneď rozhoduje, či bude treba obetovať vedúcich. Ak áno, odčíta počet obetovaných vedúcich od celkového počtu vedúcich.

Stačí nám prejsť vstupom iba raz, a teda časová zložitosť riešenia je \(O(n)\). Pri čítaní nám stačí si pamätať iba aktuálnu výšku skaly, a teda pamäťová zložitosť riešenia je \(O(1)\).

n, poc_v, skok = map(int, input().split())
vysky = list(map(int, input().split()))

for v in vysky:
    if skok < v:
        poc_v -= v-skok

print(max(0, poc_v))
#include <iostream>

auto main() -> int
{
    long long n = 0, v = 0, k = 0;
    std::cin >> n >> v >> k;

    for (auto i = 0, x = 0; i < n && v > 0; ++i) {
        std::cin >> x;
        v -= std::max(0ll, x - k);
    }

    std::cout << std::max(0ll, v) << '\n';
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.