4. Perníková optimalizácia vzorové riešenie

7 9
3 5 11

9 10 11 12 15 18 20 21 22

42 6
1 2 3

42 43 44 45 46 47

Spôsobov ako riešiť túto úlohu je mnoho. V tomto vzorovom riešení sa postupne pozrieme na zopár z nich, začínajúc od najmenej efektívnych.

Ako prvé asi každému napadne nasledovné riešenie – budeme postupne skúšať čísla \(n\) a vyššie a pre každé overovať, či vyhovuje podmienkam zadania (teda či je deliteľné aspoň jedným z čísel \(a,b,c\)). Akonáhle nájdeme \(m\) vyhovujúcich čísel, môžeme skončiť.

Takéto riešenie úspešne zvládne prvé tri testovacie sady, na zvyšné je však príliš pomalé. Čísel, ktoré musíme vyskúšať, je v najhoršom prípade až \(m \cdot min(a,b,c)\), čo je vzhľadom na veľkosti vstupov zhruba \(m^2\). To znamená, že náš algoritmus bude musieť v najhoršom prípade urobiť zhruba \(m^2\) krokov. Povedané odbornejšie, jeho časová zložitosť je \(O(m^2)\). Takéto riešenie je pomalé pre \(m\) väčšie ako pár tisíc.

#include <iostream>

using namespace std;

int main() {
    long long n, m, a, b, c;
    cin >> n >> m;
    cin >> a >> b >> c;
    int pocet = 0;
    while (pocet < m) {
        if(n%a == 0 || n%b == 0 || n%c == 0) {
            cout << n;
            pocet++;
            if(pocet == m) cout << endl;
            else cout << " ";
        }
        n++;
    }
}

Ak chceme zlepšiť náš algoritmus, musíme vymyslieť spôsob ako neskúšať veľa zbytočných čísel. Uvedomme si, že čísla, ktoré máme vrátiť na výstup sú všetko násobky čísel \(a\), \(b\) alebo \(c\). Určite teda nebudeme potrebovať viac ako prvých \(m\) násobkov \(a\) väčších ako \(n\), prvých \(m\) násobkov \(b\) väčších ako \(n\) a prvých \(m\) násobkov \(c\) väčších ako \(n\). Všetky čísla, ktoré máme vypočítať sa musia nachádzať medzi týmito \(3m\) číslami.

Poďme sa preto pozrieť, ako by sa dala vygenerovať postupnosť násobkov čísla \(a\) väčších ako \(n\) alebo rovných \(n\).

V prvom rade treba nájsť najmenší prvok – teda najmenšie číslo deliteľné \(a\), ktoré je väčšie alebo rovné \(n\). Vo väčšine programovacích jazykoch máme celočíselné delenie. To znamená, že podiel \(n/a\) sa zaokrúhľuje nadol a ak je jeho výsledok číslo \(x\), tak platí, že \(x \cdot a \leq n\). Ak si teda napríklad v C++ zoberieme výraz (n/a) * a, nedostaneme hodnotu \(n\), ale násobok čísla \(a\), ktorý nie je väčší ako \(n\).

V tomto momente musíme rozlíšiť dve možnosti. Ak je \(n\) deliteľné číslom \(a\), tak \(n\) je najmenší násobok čísla \(a\), ktorý je väčší alebo rovný \(n\). V opačnom prípade, ak číslo \(n\) nie je deliteľné \(a\), je týmto najmenším vhodným násobkom číslo (n/a) * a + a (ak sme mali najväčší násobok \(a\) menší ako \(n\), tak pričítaním \(a\) dostaneme násobok väčší ako \(n\)).

Ak však nechceme písať zbytočné if-y na rozlišovanie týchto dvoch možností, dá sa to zhrnúť aj do jedného výrazu ((n+a-1)/a) * a (v iných jazykoch analogicky). Uvedomte si, že ak \(n\) bolo deliteľné \(a\), tak výsledok (n+a-1)/a bude rovnaký ako n/a, lebo podiel sa zaokrúhlil nadol, ak však \(n\) malo nejaký zvyšok po delení \(a\), tak hodnota (n+a-1)/a bude rovná (n/a)+1, čo je presne to, čo sme chceli. (Pozor si treba dať v Pythone, kde sa celočíselné delenie zapisuje dvoma lomkami n//a.)

No a ak máme najmenšie číslo, všetky nasledujúce násobky získame pripočítavaním čísla \(a\), čo vieme spraviť v jednom for cykle. Samozrejme, pre čísla \(b\) a \(c\) funguje úplne rovnaký postup.

#include <iostream>

using namespace std;

long long pole[1000000]; // dostatocne velke pole

void postupnost(long long n, int m, long long a) {
    long long zac = ((n+a-1)/a) * a;
    for (int i = 0; i < m; i++) {
        pole[i] = zac;
        zac += a;
    }
}

Ostáva otázka, čo spraviť s týmito troma postupnosťami \(m\) čísel a ako z nich získať výslednú odpoveď. Predstavme si, že ich dáme všetky dokopy a usporiadame od najmenšieho po najväčšie, pričom vyhádžeme duplikáty (opakujúce sa čísla). Potom prvých \(m\) čísel z toho, čo nám zostane bude odpoveďou na našu úlohu.

V tomto mometne niektorí z vás vedia naprogramovať nasledovný algoritmus: pre každé z čísel \(a\), \(b\) a \(c\) si vypočítame prvých \(m\) čísel väčších ako \(n\) a deliteľných týmto číslom. Tieto tri postupnosti spojíme do jedného poľa a toto pole usporiadame nejakým štandardným knižničným algoritmom. Následne prejdeme toto usporiadané pole a vždy keď narazíme na číslo, ktoré sme ešte nevypísali (je iné ako predchádzajúce číslo), tak ho vypíšeme. Keď vypíšeme \(m\) čísel algoritmus zastavíme.

Problém ale je, že sme museli použiť triedenie z nejakej knižnice (čo síce môžete robiť ak to poznáte, ale nie všetci to vedia) a časová zložitosť tohto riešenia nie je optimálna, lebo triedenie je o niečo pomalšie (o pomerne málo, takže takéto riešenie vám pravdepodobne aj tak pobehá na plný počet bodov, to však nie je dobrý pohľad).

Potrebujeme teda vymyslieť spôsob, ako získať \(m\) najmenších čísel z troch postupností. Ešte sme nevyužili fakt, že čísla v týchto postupnostiach sú už usporiadané od najmenšieho po najväčšie. Predstavme si, že máme tri postupnosti kartičiek, na ktorých sú napísané rôzne čísla. V každej postupnosti sú však tieto čísla usporiadané zľava doprava rastúco. Naším cieľom je vytvoriť z týchto troch postupností jednu spoločnú, usporiadanú postupnosť, ktorá neobsahuje rovnaké čísla viackrát.

Ktoré číslo môže byť na začiatku tejto výslednej postupnosti? Iba jedno z troch naľavejších kartičiek, na ktorých sú najmenšie čísla daných postupností. No a samozrejme, to najmenšie z nich. Pozrieme sa teda na začiatky postupností, zistíme, ktoré číslo má byť ako prvé a túto kartičku odoberieme a položíme ako prvú kartičku výslednej postupnosti. Naviac, aby sme sa zbavili duplikátov, tak ak najmenšie číslo bolo na viacerích najľavejších kartičkách, tie zvyšné zahodíme.

No a tento postup môžeme opakovať. Ak chceme vedieť, ktoré číslo bude na druhom mieste, opäť budeme hľadať na začiatku troch postupností, ktoré teraz vyzerajú trošku ináč, lebo sme niektorím odstránili najmenší prvok. Takto pokračujeme až kým sa nám neminú všetky postupnosti kartičiek.

Ak sme si teda nami vygenerované tri postupnosti deliteľov čísel \(a\), \(b\) a \(c\) uložili do troch polí, môžeme \(m\) krát zopakovať vyššie popísaný postup a získať správnu odpoveď. Vyhadzovanie kartičiek zo začiatkov polí implementujeme tak, že si pre každé z našich troch polí budeme v jednej premennej pamätať, kde sa v ňom nachádza prvá nevyhodená kartička. Ak chceme z daného poľa prvú kartičku vyhodiť, túto premennú zvýšime o 1.

V zadaní sa však písalo, že táto úloha sa dá riešiť bez toho, aby sme použili nejaké polia.

Už sme si povedali, že vieme vypočítať najmenšie násobky čísel \(a\), \(b\) a \(c\), ktoré sú väčšie alebo rovné \(n\). Označme si tieto najmenšie násobky \(x\), \(y\) a \(z\). Je jasné, že prvé číslo, ktoré chceme vypísať na výstup bude číslo \(\min(x,y,z)\), lebo sú to najmenšie čísla našich postupností. Nech napríklad toto najmenšie číslo je \(x\) a navyše \(x=y\). Potom tieto dve čísla už nemôžeme použiť a hľadáme ďalšie násobky čísel \(a\) a \(b\). Ale to sú samozrejme čísla \(x+a\) a \(y+b\) (ak budeme potrebovať ďalší násobok čísla \(c\), bude to \(z+c\)). Vieme teda upraviť hodnotu \(x\) aj \(y\) a pokračovať rovnakým spôsobom. Opäť sa pozrieme na minimum \(x\), \(y\) a \(z\), vypíšeme ho a príslušné premenné zväčšíme o príslušnú hodnotu (čo je v podstate to isté, ako keď sme v kartičkovom riešení vyhadzovali najľavejšiu kartu z radu). Toto zopakujeme \(m\) krát, čím získame výsledok.

Na toto riešenie nám stačí zopár premenných a nepotrebujeme použiť žiadne pole. O takýchto riešeniach hovoríme, že majú konštantnú pamäťovú zložitosť, čo zapíšeme ako \(O(1)\). Čo sa týka rýchlosti tohto algoritmu, musíme urobiť rádovo \(m\) operácií, takže časová zložitosť je \(O(m)\).