3. Strašná kopa papierov (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

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?

Úloha

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.

Formát vstupu

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.

Obmedzenia

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\).

Formát výstupu

Vypíšte jedno celé číslo – počet obrázkov, ktoré budú viacfarebné.

Príklad

Input:

Output:

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:

Output:

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:

Output:

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.

Priamočiare riešenie

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.

Ako to zlepšiť ?

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.

Časová zložitosť :

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.

Pamäťová zložitosť :

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)

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ť.

3. Strašná kopa papierov vzorové riešenie

Zadanie

Úloha

Formát vstupu

Obmedzenia

Formát výstupu

Príklad

Priamočiare riešenie

Ako to zlepšiť ?

Časová zložitosť :

Pamäťová zložitosť :

Diskusia