2. Absurdne drahá pizza vzorové riešenie

3 2 3
2 0 6

7

3 0 2
1 2 3

3

1 1 11
1

4

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()))