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.
Ako prvé si môžeme všimnúť, že políčka, na ktorých sa môže figúrka po $k$ ťahoch nachádzať, budú tvoriť súvislý úsek. Teda to budú všetky políčka z intervalu $\langle 1,x \rangle$. Prečo to ale platí? Pozrime sa na políčko, z ktorého sme sa dostali na posledné políčko tohto intervalu. Ak by sme z neho skočili o menej políčok, dokázali by sme sa dostať na všetky políčka medzi nimi. Toto platí pre všetky políčka, na ktoré skočí figúrka na ceste z políčka $1$ na posledné políčko.
Môžeme si všimnúť, že z nejakého políčka $i$ dokážeme skočiť na $a_i$ políčok dopredu a $a_i$ políčok dozadu. Dozadu sa ale skákať neoplatí, lebo na ľubovoľné políčko pred $i$ sa vieme dostať na aspoň toľko ťahov ako na políčko $i$. Takto nám vznikol nejaký graf, kde políčka sú vrcholy a hrana z políčka $i$ na políčko $j$ vedie vtedy, ak sa dá z $i$ doskočiť na $j$. Keď už máme tento graf, tak dokážeme jednoducho pomocou prehľadávania do šírky1 nájsť najkratšiu cestu z políčka $1$ na políčko $n$. Toto riešenie bude ale mať časovú zložitosť až $O(n \cdot max(a_i))$, lebo z každého vrchola môže ísť až $max(a_i)$ hrán.
Toto riešenie by v c++ mohlo vyzerať takto:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,policko;
cin>>n;
vector<int> policka,vzdialenost(n,-1);
for(int i = 0;i < n;i++){ //nacitanie vstupu
cin >> policko;
policka.push_back(policko);
}
queue<int> fronta;
fronta.push(0);
vzdialenost[0] = 0;
while(!fronta.empty() && vzdialenost[n-1] == -1){
int teraz = fronta.front();
fronta.pop();
for(int i = teraz + 1; i <= teraz + policka[teraz] && i < n; i++){
if(vzdialenost[i] == -1){ //ak sme este neboli na novom policku, pridame ho do fronty
fronta.push(i);
vzdialenost[i] = vzdialenost[teraz] + 1;
}
}
}
cout<< vzdialenost[n-1] <<endl;
}
Označme si najvzdialenejšie políčko, na ktoré sa vieme dostať pomocou $k$ ťahov ako $X_k$. Keďže z políčok $1$ až $X_{k-1}$ sa dá dostať najďalej na políčko $X_k$, tak ďalší najlepší ťah pôjde z jedného z políčok $X_{k-1} + 1$ až $X_k$. Z každého z nich teda môžeme skúsiť skočiť ďalej.
Takýmto spôsobom prejdeme každé políčko najviac raz, teda časová zložitosť bude $O(n)$. Vzorové riešenie v Pythone môže vyzerať napríklad takto:
# nacitanie vstupu
n = int(input())
policka = list(map(int, input().split()))
zaciatok = 0
koniec = 0
najlepsie = 0
vysledok = 0
while(koniec < n-1): # kym sa nevieme dostat do ciela, potrebujeme pridat este jeden tah
for i in range(zaciatok, koniec+1): # zistenie najlepsieho policka, na ktore sa vieme dostat pouzitim vysledok + 1 tahov
najlepsie = max(najlepsie, i + policka[i])
vysledok += 1
zaciatok = koniec + 1 # zo starych policok uz nema zmysel skakat, teda nas uz nemusia zaujimat
koniec = najlepsie
print(vysledok)
Pamäťová zložitosť sa dá ešte zlepšiť na $O(1)$ tým, že čísla zo vstupu budeme načítavať postupne počas riešenia úlohy. Takéto riešenie v C++ by mohlo vyzerať napríklad takto:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
int zaciatok = 0,koniec = 0,najlepsie = 0,vysledok = 0,policko;
while(koniec < n - 1){ //kym sa neviem dostat do ciela, potrebujem pridat este jeden tah
for(int cur = zaciatok; cur <= koniec; cur++){ //prejdem kazde policko, na ktore sa viem dostat pomocou vysledok + 1 tahov
cin >> policko;
najlepsie = max(najlepsie,cur + policko);
}
vysledok++;
zaciatok = koniec+1; //zo starych policok ma nezaujimaju uz tie, ktore som presiel
koniec = najlepsie;
}
cout << vysledok << endl;
}