5. LTT

Boli ste neposlušní darebáci a za trest vás odsúdili do LEGO® Tunela Trýznenia™. Tento tunel je dlhočížny a aby toho nebolo málo, jeho podlaha je posiata LEGO kockami. Jooj LEGO na zemi. Au au.

Spoločnosť LEGO sa aj v Tuneli Trýznenia snaží rozvíjať rozum a plánovanie. Na každom metri tunela sú umiestnené tenučké šľapky. Tie síce nijako nezmiernia bolesť spôsobenú dánskym plastom, ale dovolia vám robiť kroky väčšej dĺžky. Konkrétne, ak máte na nohách šľapky s veľkosťou \(v\), môžete urobiť krok dĺžky \(v\) metrov.

Netušíte ako je to možné, neviete prečo takéto šľapky nepredávajú armáde a bojíte sa pýtať. Ale to nie je dôležité. Dôležité je, že vám to umožní prejsť tunelom na menej krokov, a teda aj menej bolesti.

A tak teraz stojíte bosí na začiatku tunela, vedľa vás položené tenučké šľapky. Hľadíte do tunela a premýšľate. Kde sa prezúvať? Koľko krokov treba spraviť? Čo bude na večeru?

Úloha

Tunel je reprezentovaný ako postupnosť \(n\) čísel \(v_0, v_1, \ldots, v_{n-1}\), kde \(v_i\) je veľkosť šľapiek na \(i\)-tom metri tunela. Na začiatku stojíte na nultom metri tunela a vašou úlohou je vyjsť von z tunela (teda stúpiť kamkoľvek do vzdialenosti aspoň \(n\)) na najmenší možný počet krokov. Na každom metri tunela môžete urobiť krok dĺžky \(v\) metrov, ak máte na nohách šľapky veľkosti \(v\). Na začiatku nemáte na nohách žiadne šľapky. Môžete si šľapky prezuť kedykoľvek tak, že šľapky ktoré máte (alebo nemáte) na nohách vymeníte s tými, na ktorých stojíte.

V popise nezabudnite napísať zložitosti a ich poriadne dôkazy. Riešenia s časovou zložitosťou \(O(n^2)\) alebo horšou nebudú za plný počet bodov.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 20\,000\)) a slovo \(smer\) udávajúce počet šľapiek v tuneli a dovolený smer pohybu. Ak je \(smer\) rovný one, môžete sa pohybovať len dopredu, ak je \(smer\) rovný two, môžete sa pohybovať aj dozadu (ale nesmiete stúpiť na zápornú súradnicu).

V druhom riadku je postupnosť \(n\) čísel \(v_0, v_1, \ldots, v_{n-1}\) (\(1 \leq v_i \leq n\)) udávajúca veľkosti šľapiek na jednotlivých metroch tunela.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo – najmenší počet krokov, ktorými môžete prejsť za koniec tunela.

Príklad

Input:

6 one
1 2 4 1 2 1

Output:

3

Na začiatku sa prezujeme do šľapiek 1, potom spravíme dva kroky a prezujeme sa do šľapiek 4 a už nám stačí len jeden krok do cieľa. Keby sme sa prezuli do šľapiek 2, museli by sme urobiť štyri kroky (lebo nestačí stúpiť na posledné šľapky).

Tipové okienko

Pripomíname, že je odporúčané Python kód nemať v globálnom skôpe, ale zabaliť ho do funkcie¹.

Dnešný nový tip je zase pre používateľov jazyka C++. Ak používate dynamické štruktúry, oplatí sa ich inicializovať na začiatku na veľkosť, ktorú budete potrebovať. Funkcia reserve je prítomná nielen na std::vector, ale aj std::unordered_map a iných.

V podobnom duchu sa toto tiež oplatí použiť keď pracujeme napríklad s dynamickým intervalovým stromom. Tento prístup sa volá bump allocator a funguje rovnako ako reserve s std::vector. Na začiatku si rezervujeme veľkú časť pamäte pre Node structy a potom si ich postupne berieme ako nám treba. Toto nám ušetrí veľa alokácii pri volaní new.

Nie vždy je toto nutné robiť, ale ak sú alokácie bottleneck, vieme touto metódou dosiahnuť veľké zrýchlenie.