Priamočiare riešenie

Najjednoduchšie riešenie je krok po kroku odsimulovať, ako sa mení počet kváskov. Vieme to urobiť tak, že budeme mať pole, kde na indexe $i$ budeme mať čas kvásku $i$. Potom stačí $t$ krát prejsť celé pole, a každému kvásku znížiť čas o $1$. Ak je nový čas kvásku rovný $0$, tak na koniec poľa pridáme $k$ nových kváskov s časom $8$, a tomuto kvásku nastavíme čas opäť na $6$. Je treba si dať pozor, aby sme v tomto prechode poľom časy novopridaných kváskov už nezmenšovali, alebo aby sme pridávali nové kvásky s vekom $9$ a teda po prejdení celého poľa mali tieto kvásky správny čas.

Výsledok, počet kváskov po $t$ dňoch je rovný dĺžke poľa.

Čo sa týka časovej zložitosti, tak náš program $t$ krát prejde celé pole. Pole bude mať na konci dĺžku najviac $nk^{t/6}$. Prečo? Ak si predstavíme, že by mali všetky kvásky rovnaký čas, a nové kvásky by vznikali s časom $6$, tak každých $6$ dní by z sa počet kváskov zväčšil $k$ krát. To znamená, že po $6$ dňoch by sa počet kváskov zväčšil na $k$ násobok, po $12$ dňoch na $k \cdot k = k^2$ násobok, a po $t$ dňoch na $k^{t/6}$ násobok. (Všimnite si, že sme urobili horný odhad, keďže sme predpokladali, že nové kvásky vznikajú s menším časom, a teda v skutočnosti z nich nové kvásky vzniknú skôr.) Pole teda prejdeme $t$ krát, a vždy bude mať dĺžku najviac $nk^{t/6}$.

Časová zložitosť je teda rovná tomu, že $t$ krát prejdeme pole s maximálnou dĺžkou $nk^{t/6}$, takže $O(t \cdot nk^{t/6})$. Pamäťová zložitosť je rovná výslednej dĺžke poľa, teda $O(nk^{t/6})$.

Takéto riešenie stačí na prvé $2$ sady.

#include<iostream>
#include<vector>

using namespace std;

int main(){
    long long n,k,t;
    int max_cas_kvasku = 7;
    int cas_noveho_kvasku = 8;
    cin>>n>>k>>t;

    vector<long long> kvasky;

    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        kvasky.push_back(tmp);
    }

    for(int c=0;c<t;c++){
        for(int i=kvasky.size()-1;i>=0;i--){
            if(kvasky[i]==0){
                for(int j=0;j<k;j++)
                    kvasky.push_back(cas_noveho_kvasku);
                kvasky[i]=max_cas_kvasku;
            }
            kvasky[i]--;
        }
    }

    cout<<kvasky.size()<<endl;

    return 0;
}

#!/usr/bin/env python3

max_cas_kvasku = 7
cas_noveho_kvasku = 8

n, k, t = map(int, input().split())
kvasky = list(map(int, input().split()))

for i in range(t):
    pocet_novych_kvaskov = 0

    for j in range(len(kvasky)):
        if kvasky[j] == 0:
            kvasky[j] = max_cas_kvasku - 1
            pocet_novych_kvaskov += 1
        else:
            kvasky[j] -= 1

    kvasky += [cas_noveho_kvasku for i in range(pocet_novych_kvaskov*k)]

print(len(kvasky))

Vzorové riešenie

Môžeme si uvedomiť, že v predchádzajúcom riešení robíme pre všetky kvásky v zásade tú istú vec: zmenšíme ich čas, a poprípade pridáme nejaké nové. Takéto niečo ale nemusíme robiť pre každý kvások zvlášť, môžeme to robiť pre všetky kvásky s rovnakým časom spolu. Ak máme napríklad tri kvásky, a z každého z nich ide akurát vzniknúť $6$ nových, tak dokopy vieme povedať, že z nich vznikne $18$ nových kváskov s vekom $8$.

Skúsme si teda namiesto poľa, v ktorom na indexe $i$ máme čas kvásku $i$ pamätať kvásky inak. Pamätajme si ich tak, že v poli na indexe $i$ budeme mať počet kváskov s časom $i$. Takto dosiahneme, že dĺžka poľa sa nebude zväčšovať, ale bude mať vždy dĺžku $9$ (keďže najväčší možný čas kvásku je $8$).

Ako teda presne budeme simulovať rast kváskov?

Opäť $t$ krát prejdeme celé pole, a kvásky na indexoch $1$ až $8$ posunieme na o $1$ menší index (zmenšíme im čas o $1$), kvásky na indexe $0$ pripočítame ku kváskom na indexe $6$ a vytvoríme príslušný počet nových kváskov s časom $8$. Treba si dať pozor na to v akom poradí to robíme, aby sme kvásky z indexu $0$, ktoré presunieme na index $6$ už viac neposúvali.

Výsledok, teda počet kváskov zistíme tak, že spočítame počty kváskov s jednotlivými časmi.

Náš program $t$ krát prejde celé pole, a každý raz urobí niekoľko málo operácií (pripočítanie a vynásobenie zopár čísel). Pole má celý čas dĺžku $9$, a prejdeme ho $t$ krát, takže časová zložitosť je $O(9t) = O(t)$.

Čo sa týka pamäťovej zložitosti, tak náš program si okrem niekoľko málo premenných pamätá len pole dĺžky $9$, takže pamäťová zložitosť je $O(9) = O(1)$.

#include<iostream>
#include<vector>

using namespace std;

int main(){
    long long n,k,t;
    int max_cas_kvasku = 7;
    int cas_noveho_kvasku = 8;
    cin>>n>>k>>t;

    vector<long long> pocty_kvaskov(cas_noveho_kvasku+1, 0);

    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        pocty_kvaskov[tmp]++;
    }

    for(int i=0;i<t;i++){
        long long nove_kvasky = pocty_kvaskov[0];
        for(int j=0;j<cas_noveho_kvasku;j++){
            pocty_kvaskov[j] = pocty_kvaskov[j+1];
        }
        pocty_kvaskov[cas_noveho_kvasku] = nove_kvasky*k;
        pocty_kvaskov[max_cas_kvasku-1] += nove_kvasky;
    }

    long long pocet_kvaskov = 0;
    for(int i=0;i<=cas_noveho_kvasku;i++)
        pocet_kvaskov += pocty_kvaskov[i];
    cout<<pocet_kvaskov<<endl;

    return 0;
}

#!/usr/bin/env python3

max_cas_kvasku = 7
cas_noveho_kvasku = 8

n, k, t = map(int, input().split())
kvasky = list(map(int, input().split()))

pocty_kvaskov = {i:0 for i in range(0, cas_noveho_kvasku+1)}
for i in kvasky:
    pocty_kvaskov[i] += 1

for i in range(t):
    nove_kvasky = pocty_kvaskov[0]

    for j in range(1, max_cas_kvasku):
        pocty_kvaskov[j-1] = pocty_kvaskov[j]

    pocty_kvaskov[max_cas_kvasku-1] = nove_kvasky

    pocty_kvaskov[max_cas_kvasku-1] += pocty_kvaskov[max_cas_kvasku]
    pocty_kvaskov[max_cas_kvasku] = pocty_kvaskov[cas_noveho_kvasku]
    pocty_kvaskov[cas_noveho_kvasku] = nove_kvasky * k

print(sum(pocty_kvaskov.values()))