Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.
*Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Merlinovi na [email protected] alebo Miškovi na [email protected] *
Počas dlhých zimných večerov sa Merlin s Miškom chceli zahrať ich obľúbenú spoločenskú hru, Chlapče, nemosúr sa!. Nastal ale menší problém, Merlin spapal kocku. Po dlhom rozmýšľaní sa rozhodli, že si hru zahrajú s trochu pozmenenými pravidlami.
Merlin s Miškom na každé z $n$ políčok napísali číslo $a_i$, najväčší počet políčok, o ktorý sa figúrka z tohto políčka môže pohnúť. Nezabúdajte, že figúrka sa môže pohnúť aj o menej ako $a_i$ políčok. Na koľko najmenej ťahov sa teraz dokáže dostať figúrka zo začiatočného na koncové políčko?
Na prvom riadku vstupu dostanete číslo $n$ ($2 \leq n \leq 10^6$), počet políčok na hracom plániku. V druhom riadku nasleduje $n$ čísel. Číslo $a_i$ ($1 \leq a_i \leq 10^6$) je číslo napísané na $i$-tom políčku.
Vypíšte jedno číslo, najmenší počet ťahov potrebný na dostanie figúrky z políčka číslo $1$ na políčko číslo $n$.
Existuje 5 sád vstupov. Pre prvú sadu navyše platí, že $n \leq 100$. Pre druhú sadu platí, že $n \leq 10^4$. Pre tretiu sadu platí, že $max(a_i) \leq 10$. Posledné dve sady nemajú žiadne ďalšie obmedzenia.
4
1 3 2 1
2
7
2 2 1 2 1 1 5
4
Figúrku môžeme postupne posúvať o 1, 2, 2 a 1 políčko, čím sa dostaneme na koniec.