Žaba sa jedného dňa rozhodol ísť na prechádzku. Keďže predošlý deň výdatne pršalo, všade bolo množstvo dážďoviek. Po chvíli však našiel také, aké ešte nikdy v živote nevidel. Tieto dážďovky boli neskutočne dlhé, každá mala pozdĺž svojho tela napísané dlhé číslo neobsahujúce nuly a navyše všetky žiarili farbami od výmyslu sveta (brilantne modré, perlovorubínovo červené, opálovo zelené, antukovo hnedé, burgundské fialové, a tak podobne).
Žaba sa rozhodol, že takýchto čudesných dážďoviek by malo byť na svete viac a preto ich začne rozmnožovať delením na menšie1. Zobral si ich za hrsť a hor’ sa na vec! Po chvíli ho to však prestalo baviť. Povedal si, že ďalšiu dažďovku už nenareže len tak, hala-bala.
Dážďovku bude rezať len medzi ciframi a každý kus musí obsahovať aspoň jednu cifru. Keď chúďa dážďovku doreže, na každom kuse musí byť číslo aspoň také veľké, ako na každom kuse naľavo od neho.
Napríklad dážďovku s číslom 11131719 môže narezať na kusy 11, 13, 17, 19 alebo na kusy 1, 1, 1, 31, 719, alebo ju môže nechať celú pokope, ale nemôže ju narezať na 111, 31, 719 pretože 31 je menej ako 111.
S takýmito pravidlami už bol spokojný, zábavy s tým bude dosť. Potom si ale uvedomil, že zistiť, koľko najviac kusov vie dostať, ak bude rezať najlepším možným spôsobom, je celkom ťažké. Vedeli by ste mu s tým pomôcť?
Úloha
Dostanete postupnosť cifier, ktorá neobsahuje nuly. Zistite, na koľko najviac čísel sa dá nasekať tak, aby každé číslo bolo aspoň také veľké, ako všetky naľavo od neho.
Formálnejšie povedané, pôvodnú postupnosť cifier \(s\) máte rozdeliť na podreťazce \(s_1, s_2, \dots, s_n\), tak, aby sme zreťazením týchto podreťazcov dostali pôvodnú postupnosť, t.j., \(s_1 s_2 \dots s_n = s\). Zároveň musí vždy platiť, že \(s_i \leq s_{i+1}\) (porovnávame číselnú hodnotu, čiže \(111 > 47\)). Máte zistiť, aké najväčšie môže byť číslo \(n\) – počet podreťazcov.
Veľmi dôležitou súčasťou vášho popisu je zdôvodnenie správnosti vášho algoritmu. Dajte si na ňom záležať.
Formát vstupu
Na jedinom riadku vstupu máte postupnosť cifier, ktorej dĺžka neprekročí \(1\,000\,000\).
Formát výstupu
Na jediný riadok vypíšte jedno číslo, najväčší možný počet kusov, na ktorý je možné nasekať dážďovku.
Príklad
Input:
1234
Output:
4
Každý kus dostane po jednej cifre.
Input:
4321
Output:
2
Nijako si nepomôžeme, jediná možnosť je sekať na 4 a 321.
Input:
11131719
Output:
6
Tu je najlepšie nasekať postupnosť na čísla 1, 1, 1, 3, 17, 19.
Nikto mu nepovedal, že u väčšiny druhov prežije len jediná časť, tá s opaskom.↩
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.