Doprogramovanie do: 13. február 2023 23:59
11 dní
Popisy už neodovzdávajte. Ešte stále však môžete odosielať vaše programy, za ktoré dostanete časť bodov.
Počet bodov:
Popis:  12b
Program:  8b

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.

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.