Zadanie
Miestnosť T2, niekedy začiatkom novembra:
“Už ste to počuli? Zdraželi pizzu v matickej jedálni! Čo budeme teraz robiť? Sme chodobní študenti, toľko si nemôžeme dovoliť zaplatiť za pizzu.”, rozliehalo sa v T2.
“Nebojte, mám plán”, povedal Krtko, “Aďo doniesie tú pizza piecku čo sľúbil, a budeme si piecť pizzu tu.”
“To by som nerobil, viete ako veľmi zdraželo droždie?”, ozval sa Kubo, ktorý sa z ničoho nič objavil v T2 tiež.
“Tak budeme robiť kváskové cesto. To len zoženieme zopár kváskov, a oni potom budú rásť samé…”
…
Tak sa aj stalo. Nakúpili sa kvásky do T2, s tým, že sa z nich bude piecť pizza. Bohužiaľ, prišiel lockdown, a vedúci prestali chodiť do T2. A tak tam kvásky len tak ležali, nikto z nich nebral, a nepozorovane sa delili na viac a viac kváskov.
Vedeli by ste vypočítať, koľko kváskov bude v T2, keď sa vrátime do školy?
Úloha
Do T2 sa nakúpilo presne \(n\) kváskov.
Rast kváskov funguje nasledovne: Každý kvások má svoj čas – počet dní do rozdelenia kvásku na viac kváskov. Tento čas je číslo od \(0\) po \(8\) (vrátane). Kvások sa rozdelí vtedy, keď je jeho čas rovný \(0\). Z každého kvásku vznikne presne \(k\) ďalších kváskov s časom \(8\). Čas pôvodného kvásku sa nastaví späť na \(6\).
Vašou úlohou je povedať, koľko kváskov bude v T2 po \(t\) dňoch.
Formát vstupu
Na prvom riadku sa nachádzajú \(3\) medzerou oddelené čísla \(n\) – počet kváskov v T2, \(k\) – počet kváskov na ktoré sa každý kvások rozdelí keď dosiahne čas 0 a \(t\) – deň, v ktorý nás zaujíma počet kváskov.
Na druhom riadku sa nachádza \(n\) medzerou oddelených čísel \(c_i\) – časy jednotlivých kváskov v deň \(0\).
Formát výstupu
Na výstup vypíšte jedno číslo, počet kváskov po \(t\) dňoch. Dajte si pozor, že toto číslo môže byť veľké. Odporúčame použiť \(64\) bitovú premennú (long long
v C/C++).
Nezabudnite za číslom vypísať znak konca riadku.
Hodnotenie
Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(20\) | \(40\) | \(50\) | \(60\) |
\(0 \leq k \leq\) | \(1\) | \(5\) | \(50\) | \(150\) |
\(1 \leq t \leq\) | \(20\) | \(40\) | \(150\) | \(180\) |
V druhej sade navyše platí, že všetky časy kváskov sa rovnajú.
Príklad
Input:
3 2 3
2 0 6
Output:
7
Kvásky budú vyzerať nasledovne. Po prvom dni vzniknú z druhého kvásky \(2\) ďalšie, a teda (ak nové kvásky pridávame na koniec) kvásky budú mať časy 1 6 5 8 8
. Po druhom dni budú mať kvásky časy 0 5 4 7 7
. Po treťom vzniknú ďalšie dva kvásky (tie opäť pridávame na koniec), a teda budú mať časy: 6 4 3 6 6 8 8
. Kváskov po \(3\) dňoch bude 7.
Input:
3 0 2
1 2 3
Output:
3
V tomto prípade z každého kvásku vznikne \(0\) ďalších, a teda sa počet kváskov vôbec nemení.
Input:
1 1 11
1
Output:
4
V tomto prípade v čase 10 budú časy kváskov 4 6 6 8
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;
>>n>>k>>t;
cin
<long long> kvasky;
vector
for(int i=0;i<n;i++){
int tmp;
>>tmp;
cin.push_back(tmp);
kvasky}
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++)
.push_back(cas_noveho_kvasku);
kvasky[i]=max_cas_kvasku;
kvasky}
[i]--;
kvasky}
}
<<kvasky.size()<<endl;
cout
return 0;
}
#!/usr/bin/env python3
= 7
max_cas_kvasku = 8
cas_noveho_kvasku
= map(int, input().split())
n, k, t = list(map(int, input().split()))
kvasky
for i in range(t):
= 0
pocet_novych_kvaskov
for j in range(len(kvasky)):
if kvasky[j] == 0:
= max_cas_kvasku - 1
kvasky[j] += 1
pocet_novych_kvaskov else:
-= 1
kvasky[j]
+= [cas_noveho_kvasku for i in range(pocet_novych_kvaskov*k)]
kvasky
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;
>>n>>k>>t;
cin
<long long> pocty_kvaskov(cas_noveho_kvasku+1, 0);
vector
for(int i=0;i<n;i++){
int tmp;
>>tmp;
cin[tmp]++;
pocty_kvaskov}
for(int i=0;i<t;i++){
long long nove_kvasky = pocty_kvaskov[0];
for(int j=0;j<cas_noveho_kvasku;j++){
[j] = pocty_kvaskov[j+1];
pocty_kvaskov}
[cas_noveho_kvasku] = nove_kvasky*k;
pocty_kvaskov[max_cas_kvasku-1] += nove_kvasky;
pocty_kvaskov}
long long pocet_kvaskov = 0;
for(int i=0;i<=cas_noveho_kvasku;i++)
+= pocty_kvaskov[i];
pocet_kvaskov <<pocet_kvaskov<<endl;
cout
return 0;
}
#!/usr/bin/env python3
= 7
max_cas_kvasku = 8
cas_noveho_kvasku
= map(int, input().split())
n, k, t = list(map(int, input().split()))
kvasky
= {i:0 for i in range(0, cas_noveho_kvasku+1)}
pocty_kvaskov for i in kvasky:
+= 1
pocty_kvaskov[i]
for i in range(t):
= pocty_kvaskov[0]
nove_kvasky
for j in range(1, max_cas_kvasku):
-1] = pocty_kvaskov[j]
pocty_kvaskov[j
-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[max_cas_kvasku] = nove_kvasky * k
pocty_kvaskov[cas_noveho_kvasku]
print(sum(pocty_kvaskov.values()))
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ť.