Zadanie

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.

Úloha

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?

Formát vstupu

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.

Formát výstupu

Vypíšte jedno číslo, najmenší počet ťahov potrebný na dostanie figúrky z políčka číslo \(1\) na políčko číslo \(n\).

Hodnotenie

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.

Príklad

Input:

4
1 3 2 1

Output:

2

Input:

7
2 2 1 2 1 1 5

Output:

4

Figúrku môžeme postupne posúvať o 1, 2, 2 a 1 políčko, čím sa dostaneme na koniec.

Prvé pozorovania

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.

Pomalé riešenie

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;
}

Vzorové riešenie

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;
}

  1. Študijný materiál o prehľadávaní do šírky↩︎

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.