4. Zajtra dávam výpoveď! vzorové riešenie

10
1 2 3 4 5 6 7 8 9 10

1020005640

7
3 9 7 5 6 7 4

3640212

13
9 4 7 8 2 3 7 4 9 7 2 3 4

9240000035012

Táto úloha sa dala riešiť viacerými spôsobmi. Ukážeme si výhody a nevýhody riešení, ktoré ste submitovali. Prvé z nich je nedostatočné, druhé vtipné ale správne, a tretie je správne a elegantné.

Hlavná myšlienka za všetkými riešeniami je nasledovná: postupne vypočítať výsledok po jednotlivých cifrách. To znamená, že najprv si vygenerujeme jednociferné číslo, ktoré spĺňa prvú požiadavku, potom k nemu pridáme ďalšiu cifru tak, aby spĺňalo druhú požiadavku, a tak ďalej. Týmto spôsobom postupne splníme všetky požiadavky, a keďže tie požadujú len deliteľnosť číslom od \(1\) po \(10\), tak sa nikdy nestane, že by nebolo možné požiadavku splniť. Toto tvrdenie si neskôr dokážeme.

Teraz sa postupne pozrieme na všetky spomínané riešenia.

Skúšanie cifry

Toto je najjednoduchšie riešenie. Výsledok máme uložený v číselnej premennej a vždy, keď dostaneme novú požiadavku, pridáme k nemu novú cifru tak, aby sme požiadavku splnili.

Urobíme to tak, že budeme postupne skúšať všetky cifry od \(0\) po \(9\). Cifru pridáme k výsledku tak, že ho vynásobíme desiatimi a pripočítame cifru. Pridáme prvú (najmenšiu) cifru, ktorá spraví výsledok deliteľný číslom z požiadavky.

n = int(input())

vysledok = 0

# postupne spracujeme všetky požiadavky
# input().split() načíta riadok vstupu a rozdelí ho podľa medzier
for poziadavka in input().split():
    poziadavka = int(poziadavka)

    # vyskúšame všetky cifry
    for cifra in range(0, 9+1):

        # prvá cifra nemôže byť nula, preto musíme tento prípad ošetriť
        if vysledok == 0 and cifra == 0:
            continue

        # pridáme cifru na koniec výsledku
        novy_vysledok = vysledok * 10 + cifra

        # ak je to deliteľné číslom z požiadavky, pridáme túto cifru
        if novy_vysledok % poziadavka == 0:
            vysledok = novy_vysledok
            break

print(vysledok)

Jedna nevýhoda tohoto riešenia je zjavná: požiadaviek na vstupe môže byť až \(200\,000\). Keďže počet cifier výsledného čísla sa rovná počtu požiadaviek, tak je jasné, že ukladať si výsledok v číselnej premennej nie je veľmi dobrý nápad. Ani do 64-bitovej premennej (napríklad long long int v C++) sa nezmestí viac ako 20-ciferné číslo.

Samozrejme, máme tu Python, a v ňom sú predsa číselné premenné neobmedzené, nie? Áno, ale zistiť zvyšok po delení sedmičkou \(200\,000\) cifernému číslu dá zabrať aj Pythonu a program nestihne vypočítať výsledok v časovom limite.

Takéto riešenie mohlo dostať najviac \(4\) body.

Zložitosť

V tomto riešení \(n\)-krát počítame zvyšky po pridaní každej možnej cifry. Počítanie zvyšku po delení má časovú zložitosť \(O(n)\)¹, kde \(n\) je počet cifier čísla, z ktorého robíme zvyšok. Ostatné operácie, ktoré v programe robíme nemajú časovú zložitosť horšiu ako \(O(n)\).

Preto je časová zložitosť tohoto programu \(O(n \cdot 10 \cdot n)\), čo sa rovná \(O(n^2)\).

Keďže si uchovávame celé výsledné číslo a toto číslo má na konci \(n\) cifier, na jeho uloženie potrebujeme \(O(n)\) pamäte.

“Orlojové” riešenie

Z predchádzajúceho riešenia je jasné, že potrebujeme vymyslieť niečo lepšie. Slabina spomínaného riešenia je v tom, že zakaždým potrebujeme vypočítať zvyšok po delení celého výsledku, čo, okrem iného, spôsobuje zlú časovú zložitosť.

Jednoduchým vylepšením bude, že si o našom výsledku budeme pamätať nejaké informácie, aby sme rýchlo vedeli vypočítať zvyšok po delení. V riešení, ktoré viete vymyslieť na základe toho, čo ste sa učili na hodinách matematiky, si môžeme pamätať takéto informácie:

• paritu, pre deliteľnosť \(2\)
• ciferný súčet, pre deliteľnosť \(3\), \(9\)
• posledné trojčíslie, pre deliteľnosť \(4\), \(5\), \(8\), \(10\)
• deliteľnosť \(6\) sa dá odvodiť z deliteľnosti \(2\) a \(3\)
• zvyšok po delení \(7\), pre deliteľnosť \(7\)

Keď si pamätáme tieto informácie, výsledok vieme generovať po cifrách tak, že postupne vyskúšame všetky cifry od \(0\) po \(9\) a na základe týchto informácii zistíme, či bude výsledok po pridaní danej cifry deliteľný číslom z požiadavky. Ak bude, tak cifru vypíšeme a aktualizujeme všetky tieto informácie.

# kód tohto programu nemusíte čítať, stačí, ak kriticky zhodnotíte jeho eleganciu

n = int(input())

vysledok = []

parne = True
ciferny_sucet = 0
posledne_trojcislie = 0
zvysok_po_7 = 0

for poziadavka in input().split():
    poziadavka = int(poziadavka)

    for cifra in range(0, 9+1):
        if len(vysledok) == 0 and cifra == 0:
            continue

        # vypočítame si, aké by boli všetky informácie, keby sme použili danú cifru
        nove_parne = cifra % 2 == 0
        novy_ciferny_sucet = (ciferny_sucet + cifra) % 9 # potrebujeme len jeho zvyšok po delení 3 a 9
        nove_posledne_trojcislie = (posledne_trojcislie * 10 + cifra) % 1000
        novy_zvysok_po_7 = (zvysok_po_7 * 10 + cifra) % 7

        # je nové číslo deliteľné číslom z požiadavky?
        dobra_cifra = False

        if poziadavka == 1:
            dobra_cifra = True
        elif poziadavka == 2:
            dobra_cifra = nove_parne
        elif poziadavka == 3:
            dobra_cifra = novy_ciferny_sucet % 3 == 0
        elif poziadavka == 4:
            dobra_cifra = nove_posledne_trojcislie % 4 == 0
        elif poziadavka == 5:
            dobra_cifra = nove_posledne_trojcislie % 5 == 0
        elif poziadavka == 6:
            dobra_cifra = nove_parne and novy_ciferny_sucet % 3 == 0
        elif poziadavka == 7:
            dobra_cifra = novy_zvysok_po_7 == 0
        elif poziadavka == 8:
            dobra_cifra = nove_posledne_trojcislie % 8 == 0
        elif poziadavka == 9:
            dobra_cifra = novy_ciferny_sucet % 9 == 0
        elif poziadavka == 10:
            dobra_cifra = cifra == 0

        if dobra_cifra:
            vysledok.append(cifra)

            parne = nove_parne
            ciferny_sucet = novy_ciferny_sucet
            posledne_trojcislie = nove_posledne_trojcislie
            zvysok_po_7 = novy_zvysok_po_7

            break

# nasledujúci príkaz vypíše vypočítané cifry výsledku pospájané do jedného reťazca
# funkcia str.join(values) vytvorí nový string tak, že string str postrká medzi všetky hodnoty values
# náš zoznam obsahuje inty, teda ich musíme najprv skonvertovať funkciou map
print(''.join(map(str, vysledok)))

Zložitosť

Keďže premenné, v ktorých si udržujeme vyššie popísané informácie dosahujú maximálne hodnoty nezávislé od veľkosti vstupu, tak práca s nimi je v konštantnom čase. Keďže musíme spracovať všetkých \(n\) požiadaviek, tak časová zložitosť je \(O(n)\).

Cifry výsledku môžeme vypisovať postupne, jednu po druhej, bez toho, aby sme si ich ukladali, teda pamäťová zložitosť môže byť až konštantná, \(O(1)\)².

Zvyšky – pôjde to aj jednoduchšie

Predošlé riešenie som nazval “orlojové”, lebo je zbytočne zložité. Pamätáme si 4 odlišné informácie a implementácia tohto riešenia obsahuje množstvo if - else alebo case príkazov – špeciálne prípady, v ktorých sa dá ľahko pomýliť.

Skúsme teda zjednodušiť myšlienku a tým aj implementáciu. Pre deliteľnosť sedmičkou sme si pamätali zvyšok po delení sedmičkou… A nedá sa to tak spraviť pre všetky cifry? Áno, dá! V tomto jednoduchšom riešení si budeme pamätať zvyšky po delení všetkými číslami od \(1\) po \(10\). Pre novú požiadavku skúsime postupne pridávať novú cifru, a vyberieme najmenšiu vyhovujúcu. V predošlom riešení tak stačí nahradiť if - else príkazy jedným for-cyklom a namiesto počítania 4 špecifických premenných spočítame v jednom for-cykle nové zvyšky po delení číslami \(1\) až \(10\), uložené v poli.

n = int(input())

vysledok = []

# v zozname si pamätáme zvyšky po všetkých číslach od 1 po 10
zvysok = [0] * 11 

for poziadavka in input().split():
    poziadavka = int(poziadavka)

    cifra = None

    # ošetríme prvú cifru
    if len(vysledok) == 0:
        cifra = poziadavka

    # zistíme, akú cifru potrebujeme pridať
    else:
        for i in range(0, 9+1):
            if (zvysok[poziadavka] * 10 + i) % poziadavka == 0:
                cifra = i
                break

    vysledok.append(cifra)

    # aktualizujeme všetky zvyšky
    for i in range(1, 10+1):
        zvysok[i] = (zvysok[i] * 10 + cifra) % i

print(''.join(map(str, vysledok)))

Zložitosť

S časovou zložitosťou je to v tomto riešení rovnaké ako v prechádzajúcom, “orlojovom”. Máme pole s konštantnou veľkosťou, ktorého prvky môžu nadobúdať len ohraničené hodnoty, nezávislé od \(n\). Práca s nimi je teda v konštantnom čase, a keďže spracúvame všetky požiadavky, tak celková časová zložitosť je \(O(n)\).

Pamäťová zložitosť je na tom rovnako, ako v prechádzajúcom riešení, ak by sme cifry vypisovali jednu po druhej, bola by konštantná, \(O(1)\), ale keďže to kvôli výkonu nerobíme, tak je lineárna, \(O(n)\).

Počítanie namiesto skúšania možností

Na záver si môžeme uvedomiť, že keď poznáme zvyšky po delení všetkými potrebnými číslami, už nepotrebujeme skúšať všetky cifry. Potrebnú cifru vieme vypočítať!

Výpočtom ďalšej cifry tiež dokážeme, že pre ľubovoľné číslo a ľubovoľnú požiadavku existuje cifra, ktorú vieme pridať. Toto tvrdenie sme využívali vo všetkých predošlých úvahách, no neboli sme presvedčení o tom, že skutočne platí.

Čo musí spĺňať cifra, ktorú chceme pridať? Výsledok po pridaní tejto cifry musí byť deliteľný číslom z požiadavky. Musí teda platiť, že nový zvyšok po delení číslom požiadavky sa rovná nule. Ak \(Z_i\) je zvyšok doteraz napísaného čísla po delení \(i\), \(p\) je požiadavka a \(c\) je cifra, ktorú pridávame, tak musí platiť toto:

\[ (Z_p \cdot 10 + c) \bmod p = 0 \]

Z tohto vzorca si jednoducho odvodíme, ako vypočítať želanú cifru:

\[ c = (- Z_p \cdot 10) \bmod p \]

Ak by ste mali vy alebo váš programovací jazyk problém počítať zvyšky záporných čísel, môžeme si uvedomiť, že \((- Z_p \cdot 10) \bmod p = (p \cdot 10 - Z_p \cdot 10) \bmod p\).

Iný spôsob, ako sa dopracovať k \(c\) je pouvažovať: Doteraz napísané číslo má zvyšok \(Z_p\). Po pridaní cifry 0 bude mať zvyšok \((Z_p \cdot 10) \bmod p\). O koľko potrebujeme zväčšiť pridanú cifru, aby sme zvyšok \((Z_p \cdot 10) \bmod p + c\) dostali na nulu? Jednoducho o \(p - (Z_p \cdot 10) \bmod p\). Ak však \((Z_p \cdot 10) \bmod p = 0\), nechceme pridať cifru \(p\), ale cifru \(0\) a to dosiahneme takto ďalším zmodulovaním \(p\):

\[ c = (p - (Z_p \cdot 10) \bmod p) \bmod p \]

Počítanie novej cifry nám prinesie len zrýchlenie o konštantu, no dôležitá je myšlienka, že nová cifra sa vždy dá pridať. Ak by napríklad mohla byť požiadavka \(11\), mohli by sme sa dostať do situácie, že doteraz napísané číslo má \((Z_{11} \cdot 10) \bmod 11 = 1\). V takomto prípade by žiadna cifra výsledný zvyšok nedotiahla na nulu.

Optimalizované zvyšky

Riešenie so zvyškami je úplne dobré. Avšak, ak sme veľkí fajnšmekri, môžeme riešenie ešte raz konštantne zrýchliť. Nemusíme si zvyšky pamätať jednotlivo v zozname, stačí, ak si budeme pamätať zvyšok po najmenšom spoločnom násobku čísel \(1\) až \(10\) a z toho si vždy vieme vypočítať každý potrebný zvyšok. Takéto riešenie dáva v Pythone dvakrát až trikrát lepšie časy než riešenie s poľom zvyškov.

nasobok = 2 * 2 * 2 * 3 * 3 * 5 * 7

n = int(input())
vysledok = []

zvysok = 0

for poziadavka in input().split():
    poziadavka = int(poziadavka)

    cifra = None
    if len(vysledok) == 0:
        cifra = poziadavka
    else:
        cifra = (poziadavka - zvysok * 10) % poziadavka

    vysledok.append(cifra)
    zvysok = (zvysok * 10 + cifra) % nasobok

print(''.join(map(str, vysledok)))