Paulínka sa v detstve najradšej hrávala s voskovkami. V jej škôlke mali na hranie práve dve veci:
veľa voskoviek v rade za sebou,
veľa kôp papierov v rade za sebou.
Nemožno sa teda čudovať, že jej zábava, povedzme si na rovinu, nebola práve najintelektuálnejšia – celý deň si brala voskovky v poradí, v akom boli na stole, a vždy, keď si vzala nejakú voskovku, nepustila ju z rúk, až kým ju celú nevypísala. Toto robila, až zafarbila všetky papiere v škôlke. Takto jej často vznikali jednofarebné obrázky a tie sa Paulínke až tak nepáčia. Vedeli by ste zistiť, koľko z jej obrázkov bolo viacfarebných?
Paulínka má $n$ voskoviek rôznych farieb, každá má svoju dĺžku $d_i$ a $m$ kôpok papierov. V každej kôpke sa nachádza $k_i$ rovnakých čistých papierov. Na zafarbenie jedného papiera z $i$-tej kôpky potrebuje Paulínka $c_i$ dĺžky voskovky/voskoviek. Paulínka vždy vyfarbí jeden celý papier a až potom prejde na ďalší. Papiere si berie poporadí, teda vždy vyfarbí celú kôpku pred tým, ako začne brať papiere z ďalšej. Voskovky si berie tiež poporadí, a vždy až potom, ako sa jej predošlá voskovka vypíše.
Zistite, koľko obrázkov bude obsahovať viac než jednu farbu.
Je zaručené, že voskovky stačia na pokreslenie všetkých papierov.
Na prvom riadku vstupu dostanete číslo $n$ – koľko rôznych voskoviek má Paulínka. Nasleduje $n$ riadkov, kde každý riadok obsahuje celé číslo $d_i$ – dĺžku $i$-tej voskovky. Ďalší riadok obsahuje číslo $m$ – počet kôpok papierov. Nasleduje $m$ riadkov, kde $i$-ty riadok obsahuje dve celé čísla $k_i$ a $c_i$, kde $k_i$ znamená počet papierov v $i$-tej kôpke a $c_i$ je celková dĺžka voskovky, ktorú treba na zafarenie jedného papiera v $i$-tej kôpke.
Sú $4$ sady vstupov.
V prvých dvoch sadách platí, že $n \leq 10\,000$, $m \leq 1000$, $d_i, c_i, k_i \leq 1000$ a suma dĺžok voskoviek je menej ako $2\,000\,000$.
V druhých dvoch sadách platí, že $n \leq 1\,000\,000$, $m \leq 200000$, $d_i, c_i, k_i \leq 200\,000$ a suma dĺžok voskoviek je menej ako $50\,000\,000\,000$.
Vypíšte jedno celé číslo – počet obrázkov, ktoré budú viacfarebné.
Input:
2
5
5
1
2 5
Output:
0
Paulínka má dve voskovky, obe dĺžky $5$. Má jednu kôpku papierov, kde sú dva papiere, pre každý treba $5$ dĺžok voskoviek. Prvou voskovkou zafarbí prvý papier, druhou druhý. Ani jeden papier nie je viacfarebný.
Input:
2
4
6
2
1 6
1 4
Output:
1
Teraz má Paulínka dve voskovky, jednu dĺžky $4$ a druhú dĺžky $6$. Má dve kôpky papierov, v oboch je po jednom papieri. Na zafarbenie prvého papiera treba $6$ dĺžok voskoviek. Na zafarbenie druhého papiera treba $4$ dĺžok voskoviek. Keďže papiere aj voskovky Paulínka berie po poradí, tak prvou voskovkou zafarbí 4 dĺžky prvého papiera a zvyšok prvého a celý druhý zafarbí druhou voskovkou.
Input:
4
1
1
1
1
1
1 3
Output:
1
V tomto prípade má Paulínka štyri voskovky, všetky dĺžky $1$. Má jednu kôpku papierov, kde je ibe jeden papier, a na jeho zafarbenie treba $3$ dĺžky voskoviek. Tri voskovky minie na zafarbenie tohoto jediného papiera, a jedna jej ostane nepoužitá. Rôznofarebný papier je teda jeden.
Ako priamočiare riešenie nám môže napadnúť, že odsimulujeme, čo sa stane pre každý papier každej kôpky. Teda si budeme pamätať aktuálny kúsok voskovky ktorý nám ostáva a postupne pre každý papier každej kôpky sa spýtame, či je kus voskovky ktorý nám aktuálne ostáva dostatočne dlhý na jeho celé zafarbenie. Ak nie, vieme že bude viacfarebný a zapamätáme si to do výsledného počtu. Nesmieme pri tom zabudnúť “odobrať” aj časť ďalšej voskovky (ktorá sa použije na vyfarbenie), prípadne niekoľko celých a časť ďalšej, prípadne len niekoľko celých (podľa toho, koľko ešte potrebujeme na dovyfarbenie papiera). Kód by mohol vyzerať takto:
#include<iostream>
using namespace std;
int main(){
long long n,m;
cin>>n;
long long d[n];
for(int i=0;i<n;i++){
cin>>d[i];
}
cin>>m;
long long c[m], k[m];
for(int i=0;i<m;i++)
cin>>k[i]>>c[i];
long long index_pastelka=0, roznofarebne=0;
for(long long i=0;i<m;i++){
for(long long j=0;j<k[i];j++){
long long nafarbit=c[i];
bool roznofarebny_papier=false;
while(nafarbit!=0){
if(d[index_pastelka]>=nafarbit){
d[index_pastelka]-=nafarbit;
nafarbit=0;
}else{
roznofarebny_papier=true;
nafarbit-=d[index_pastelka];
d[index_pastelka]=0;
index_pastelka++;
}
if(d[index_pastelka]==0)
index_pastelka++;
}
if(roznofarebny_papier)
roznofarebne++;
}
}
cout<<roznofarebne<<endl;
}
n = int(input())
dlzky = []
for i in range(n):
dlzky.append(int(input()))
m = int(input())
skupinky = []
for i in range(m):
skupinky.append(list(map(int, input().split())))
index_voskovka = 0
ostava_z_voskovky = dlzky[index_voskovka]
roznofarebne = 0
for i in skupinky:
pocet, treba_nafarbit = i[0], i[1]
for obr in range(pocet):
treba_nafarbit = i[1]
if ostava_z_voskovky == 0:
index_voskovka += 1
ostava_z_voskovky = dlzky[index_voskovka]
if ostava_z_voskovky >= treba_nafarbit:
ostava_z_voskovky -= treba_nafarbit
else:
roznofarebne += 1
while treba_nafarbit > ostava_z_voskovky:
index_voskovka += 1
ostava_z_voskovky += dlzky[index_voskovka]
ostava_z_voskovky -= treba_nafarbit
print(roznofarebne)
Problémom ale je, že takéto riešenie nebude dostatočne efektívne, keďže potrebujeme $O(m \cdot k)$ operácií a v zadaní vidíme, že $m$ a $k$ môžu byť každé až $200\,000$. Teda potrebujeme rozhodovať o zhruba $4\,000\,000\,000$ papierov. To je priveľa a náš program to nestihne.
Tu si treba všimnúť, že ak by sme namiesto každého papiera každej kôpky prechádzali voskovkami, budeme potrebovať oveľa menej operácií, lebo podľa obmedzení, voskoviek bude najviac milión. Potom náš algoritmus bude fungovať tak, že si pamätá, koľko ostáva z aktuálnej voskovky a až kým sa neminie, berie celé kôpky a pýta sa:
dokážem z tejto voskovky zafarbiť celú kôpku ?
dokážem z tejto voskovky zafarbiť niekoľko celých papierov kôpky ? Toto sa dá jednoducho urobiť pomocou zvyšku po delení – modulo.
inak určite vznikne viacfarebný papier
Pri každom prípade treba dopočítať, koľko z aktuálnej voskovky ostane, prípadne ak potrebujeme viac ako len aktuálnu voskovku, tak si vypočítať, koľko ostane z poslednej ktorú použijeme.
Riešenie bude mať zložitosť $O(m+n)$, pretože ako si môžeme všimnúť, s každou voskovkou a každou kôpkou pracujeme iba raz. Teda ak si napríklad označíme index voskovky s ktorou práve pracujeme ako $i$, tak toto $i$ vždy rastie, nikdy neklesá (k vypísaným voskovkám sa nevraciame). Rovnako ak si označíme index kôpky ktorú práve zafarbujeme ako $j$, tak aj toto $j$ vždy rastie, nikdy neklesá (k zafarbeným kôpkam sa nevraciame). Keďže pri zafarbovaní kôpky robíme len konštantné operácie - vetvenie a delenie, tak nič iné nám zložitosť neovplyvňuje.
Aj pamäťová zložitosť bude $O(m+n)$, lebo si musíme pamätať $n$ dĺžok voskoviek, $m$ veľkostí kôpok a $m$ hodnôt opisujúcich dĺžku voskovky na zafarbenie $1$ papiera danej kôpky. Teda pamäťová zložitosť bude $O(2m + n)$, teda $O(m+n)$.
#include<iostream>
using namespace std;
int main(){
long long n,m;
cin>>n;
long long d[n];
for(int i=0;i<n;i++)
cin>>d[i];
cin>>m;
long long c[m], k[m];
for(int i=0;i<m;i++)
cin>>k[i]>>c[i];
long long index_kopky=0, index_obrazok=0, nafarbene=0, roznofarebne=0;
for(long long i=0;i<n;i++){ //iterujeme cez pastelky
while(index_kopky<m && d[i]>0){
// vieme nafarbit celu kopku resp. zvysok kopky
if(d[i]>=(c[index_kopky]*(k[index_kopky]-index_obrazok)-nafarbene)){
d[i]-=c[index_kopky]*(k[index_kopky]-index_obrazok)-nafarbene;
index_kopky++;
index_obrazok=0;
nafarbene=0;
}else{
if(d[i]<c[index_kopky]-nafarbene){ // neviem zafarbit cely obrazok
if(nafarbene==0){
roznofarebne++;
}
nafarbene+=d[i];
d[i]=0;
}else{ // viem zafarbit (aspon jeden) cely obrazok
index_obrazok++;
d[i]-=(c[index_kopky]-nafarbene);
index_obrazok+=d[i]/c[index_kopky];
nafarbene=d[i]%c[index_kopky];
d[i]-=(d[i]/c[index_kopky])*c[index_kopky];
d[i]-=nafarbene;
if(nafarbene){
roznofarebne++;
}
}
}
}
}
cout<<roznofarebne<<endl;
}
n = int(input())
dlzky = []
for i in range(n):
dlzky.append(int(input()))
m = int(input())
skupinky = []
for i in range(m):
skupinky.append(list(map(int, input().split())))
index_voskovky = 0
ostava = dlzky[index_voskovky]
roznofarebne = 0
i = 0
pocet_na_kopke = 0
treba_nafarbit = 0
while i < len(skupinky) or (i == len(skupinky) and pocet_na_kopke > 0):
if pocet_na_kopke == 0:
pocet_na_kopke, treba_nafarbit = skupinky[i][0], skupinky[i][1]
i += 1
if ostava == 0:
index_voskovky += 1
ostava += dlzky[index_voskovky]
if ostava > pocet_na_kopke*treba_nafarbit: # zafarbim celu kopku
ostava -= pocet_na_kopke*treba_nafarbit
pocet_na_kopke = 0
elif ostava == pocet_na_kopke*treba_nafarbit: # zafarbim celu kopku a miniem voskovku
ostava -= pocet_na_kopke*treba_nafarbit
pocet_na_kopke = 0
else: #zafarbim len cast kopky
if ostava % treba_nafarbit == 0: # zafarbim cele obrazky
pocet_na_kopke -= ostava//treba_nafarbit
ostava = 0
elif ostava > treba_nafarbit: # zafarbim nejake cele
pocet_na_kopke -= ostava//treba_nafarbit
ostava -= (ostava//treba_nafarbit) * treba_nafarbit
# naberiem farby pre viacfarebny
while ostava < treba_nafarbit:
index_voskovky += 1
ostava += dlzky[index_voskovky]
# zafarbim viacfarebny
roznofarebne += 1
ostava -= treba_nafarbit
pocet_na_kopke -= 1
else: # zafarbim viacfarebne jeden
# naberiem farby pre viacfarebny
while ostava < treba_nafarbit:
index_voskovky += 1
ostava += dlzky[index_voskovky]
# zafarbim viacfarebny
roznofarebne += 1
ostava -= treba_nafarbit
pocet_na_kopke -= 1
print(roznofarebne)
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete