Začneme okľukou

Väčšinou riešime úlohy od prvej sady postupne vyššie. Teraz si však vyriešime najskôr tretiu sadu, lebo zvyšné na seba nadväzujú.

V tejto sade sú všetky autobusy rovnako veľké, teda počet ľudí, ktorí prejdú na jednu zelenú križovatkou je vždy rovnaký – je jedno, ktorý autobus je momentálne prvý, lebo sú všetky rovnaké. Môžme teda napríklad odsimulovať prvú zelenú (viď bruteforce nižšie) a to následne vynásobiť $k$, ale v skutočnosti si to môžme aj jednoducho vypočítať.

Označme si počet ľudí v autobuse $a$ (toto bude rovnaké pre všetky autobusy), potom na každú zelenú prejde križovatkou $\lfloor r / a\rfloor$ autobusov, avšak križovatkou môže na každú zelenú autobus prejsť len raz, čize v skutočnosti $\min(\lfloor r/a \rfloor, n)$ autobusov. V každom autobuse je $a$ ľudí, teda za jednu zelenú prejde $\min(\lfloor r/a \rfloor, n) \times a$ ľudí. Zeleých je $k$, čiže spolu $\min(\lfloor r/a \rfloor, n) \times a \times k$ ľudí.

Časová aj pamäťová zložitosť tohoto programu bude $O(1)$.

Bruteforce

Teraz ideme riešiť prvú sadu. Keďže je zelených aj autobusov málo, môžme si dovoliť všetky zelené simulovať. Každú zelenú odsimulujeme presne tak, ako by to robil semafór na križovatke. Sčítavame si, koľko ľudí sme zatiaľ križovatkou pustili, a pokiaľ môžme pustiť aj ďalší autobus, pustíme ho. Toto riešenie bude mať zložitosť $O(kn)$ – pre každú zelenú môžeme pustiť až $n$ autobusov.

Jedna možnosť, ako to implementovať, je použiť dátovú štruktúru rad / fronta (C++ std::queue), prípadne obojstranná fronta (C++ std::deque, Python collections.deque), a naozaj autobusy vyberať spredu a vkladať dozadu.

Druhá možnosť je mať autobusy celý čas uložené v pôvodnom poradí, a pamätať si stav len ako jedno číslo: index autobusu, ktorý momentálne stojí ako prvý pred semafórom. Obe možnosti sú rovnako dobré, ale tento pohľad sa nám bude hodiť v ďalších sadách.

Podľa implementácie mohlo toto riešenie zbehnúť na 2 alebo 4 body.

Načo toľko počítame?

Pri predchádzajúcom riešení sme si mohli všimnúť dôležité pozorovanie. A to že stav po zelenej závisí iba od stavu pred zelenou. Ak sme sa počas deja viackrát nachádzali v nejakom stave $i$ (teda v situácii že autobus číslo $i$ čakal hneď pred semafórom), zakaždým semafór pustí rovnako veľa ľudí, a zakaždým bude po stave $i$ nasledovať ten istý ďalší stav.

Preto by sa nám hodilo predpočítať polia, čo o každom stave/autobuse povedia: “Ak pred zelenou čakal prvý v rade autobus $x$, tak počas zelenej prejde $c_x$ ľudí, a po nej bude čakať prvý autobus $s_x$.” S nimi budeme vedieť každú zelenú vybaviť v konštantnom čase.

Predpočítať takéto polia $c$, $s$ by sme dokázali napríklad pomocou prefixových súčtov a binárneho vyhľadávania, ale my to spravíme rýchlejšie, a dokonca bez nejakých pokročilých techník, ako prefixové súčty a binárne vyhľadávanie!!

Všimnime si, že pole $s$ je neklesajúce – o dvoch susedných autobusoch $x$, $x+1$ platí že $s_x \leq s_{x+1}$. Inak povedané, ak by som pred zelenou začínal o jeden autobus neskôr, tak po zelenej skončím na rovnakom alebo neskoršom autobuse. Platí to, pretože ak autobusy od $x$ po $s_x-1$ mohli prejsť (ich súčet ľudí je maximálne $r$), tak zaručene aj od $x+1$ po $s_x-1$ môžu prejsť (ich súčet tiež bude maximálne $r$), a možno sa zmestia aj ďalšie, takže $s_{x+1}$ musí byť aspoň $s_x$.

(Výnimka: autobusy tvoria cyklus. Chceme sa tváriť že za posledným autobusom $n-1$ ide zase $0$ a to je stále “neklesajúci” krok. V niektorých úlohách sa môže pri kódení zísť trik, prilepiť k sebe dve kópie pôvodného zoznamu. Indexy $n$ až $2n-1$ znamenajú, že sme na $0$ až $n-1$, ale už sme prešli otočku. Tu to nebolo treba.)

Vďaka neklesajúcosti môžeme použiť techniku dvoch bežcov (two pointers). Pre prvý autobus $0$ vypočítame $c_0$, $s_0$ normálne – skúšame autobusy až kým neprekročíme $r$. Pre zvyšné autobusy pri výpočte $c_{x+1}$, $s_{x+1}$ zoberieme $c_x$, $s_x$ predošlého suseda, odčítame ľudí z autobusu $x$, a začneme skúšať možné $s_{x+1}$ až od $s_x$ ďalej. Predstavme si to ako dvoch bežcov, kde zakaždým keď zadný bežec spraví jeden krok, predný bežec spraví nula alebo viac krokov tak, aby udržal náskok $r$ cestujúcich.

Aké je to celé rýchle? Zadný bežec spraví presne $n$ krokov. Predný bežec spraví maximálne $2n$ krokov, lebo jeho náskok nikdy nemôže byť väčší ako $n$ autobusov, lebo každý autobus môže na zelenú prejsť len raz. Spolu bežci spravia $O(n)$ krokov, každý spracujeme v konštantnom čase.

Máme teda riešenie v $O(n + k)$, čo pohodlne zbehne na 4 body.

Optimálne riešenie

Na optimálne riešenie si stačí uvedomiť, že stavy sa nám určite budú počas deja opakovať. Máme totiž len $n$ možných stavov (možných autobusov ktoré môžu čakať ako prvý), a každý z nich sa vždy správa rovnako. Najviac po $n+1$ zelených sa teda dostaneme do stavu v ktorom už sme boli. Odteraz sa bude všetko správať ako predtým, teda sa do neho znovu dostaneme, a tak ďalej…

Ako to využiť? Budeme si simulovať zelené podobne ako v predošlom riešení a keď sa dostaneme do stavu, v ktorom už sme boli – teda že ako prvý je autobus, ktorý už sme ako prvý niekedy mali – vieme že sa bude stále dookola opakovať sekvencia stavov, ktorú sme videli, odkedy sme sem prvýkrát prišli.

Keď do stavu $i$ prídeme prvýkrát, zapamätajme si hodnotu $d_i$ – počet zelených, po koľkých sme do toho stavu prvýkrát prišli, a $p_i$ – počet cestujúcich, čo sme do prvého príchodu videli. Keď sa vrátime do už navštíveného stavu, zistíme vďaka tomu dĺžku cyklu (počet zelených od prvej návštevy), aj koľko cestujúcich prejde za jeden cyklus.

A s týmito informáciami už vieme spočítať odpoveď. Nech dĺžka cyklu je $D$, počet ľudí, ktorí za cyklus prejdú je $P$ a cyklus začína autobusom $a$. Potom sa celý cyklus vykoná $\lfloor(k-d_a)/D\rfloor$ krát – najskôr prejdeme na začiatok cyklu, teda sa nám zmenší $k$ o $d_a$. V každom cykle prejde $P$ ľudí, spolu teda $\lfloor(k-d_a)/D\rfloor \times P$ ľudí. Nakoniec nám ešte zostalo niekoľko zelených konkrétne $(k-d_a) \mod D$, ktoré treba dokončiť. Keďže však $D\leq n$, bude aj počet zelených ktoré treba vykonať nanajvýš $n$.

Keď si to celé zhrnieme, najskôr pomocou dvoch bežcov spočítame úseky autobusov, ktoré prejdú cez križovatku, ak bude rad začínať jednotlivými autobusmi – $O(n)$. Potom odsimulujeme najviac $n+1$ zelených, kým najdeme cyklus – $O(n)$, urobíme nejaké výpočty s cyklom – $O(1)$, po čom musíme ešte odsimulovať nanajvýš $n$ ďalších zelených – $O(n)$.

Celková časová zložitosť teda bude $O(n)$, pamäťová bude rovnaká.

#include <bits/stdc++.h>

using namespace std;

int main(){
    int r, k, n; cin>>r>>k>>n;

    vector<int> a(n);
    for(int i =0;i< n;i++)cin>>a[i];
    vector<long long> next(n), pocet(n); //skupina co bude po procese prva, a pocet aut ktore za proces prejdu, ak zacinala skupina i

    long long sum = 0;
    int end = 0;
    for(int i =0;i< n;i++){
        while(sum + a[end] <=r){
            sum += a[end];
            end = (end + 1)%n;
            if(end == i) break;
        }
        next[i] = end;
        pocet[i] = sum;
        sum-=a[i];
    }

    int first_bus = 0;
    long long cycle_distance = 0, cycle_pocet = 0; //D a P zo vzoraku
    vector<long long> d(n, -1), p(n, -1); //polia d a p zo vzoraku

    while(true){
        d[first_bus] = cycle_distance;
        p[first_bus] = cycle_pocet;
        cycle_distance++;
        cycle_pocet += pocet[first_bus];
        first_bus= next[first_bus];
        if(p[first_bus]!= -1)break;
    }

    long long ans = 0;

    if(d[first_bus] <= k){
        k -= d[first_bus];
        ans += p[first_bus];
    }

    cycle_distance -= d[first_bus]; cycle_pocet -= p[first_bus];

    long long reps = k/cycle_distance;

    k-=reps*cycle_distance;

    ans += reps*cycle_pocet;

    while(k--){
        ans += pocet[first_bus];
        first_bus = next[first_bus];
    }
    cout<< ans<<endl;
}