3. Zygrov dlhoročný sen ... vzorové riešenie

1
504

510 511 512 513 514 515 516 517 518 519

3
144
585
576

150 151 152 153 154 155 156 157 158 159

590 591 592 593 594 595 596 597 598 599

Ciferný súčet

Na začiatok si povieme, ako zistiť ciferný súčet čísla \(c\). Na výpočet ciferného súčtu použijeme operáciu modulo – zvyšok po delení. Posledná cifra čísla \(c\) je zvyšok po delení číslom 10, alebo \(c \mod 10\). Vydelením čísla \(c\) číslom 10 ho “skrátime” o poslednú cifru.

Rovnakú myšlienku preto môžeme použiť aj na predposlednú cifru, predpredposlednú cifru… Postup budeme opakovať, až kým nebudeme vedieť všetky cifry. Skončíme vtedy, keď sa nám číslo zmenší na nulu. Cifry čísla \(c\) si budeme postupne sčítavať do premennej.

long long ciferny_sucet(long long cislo){
    long long sucet = 0;
    while (cislo > 0) {
        long long posledna_cifra = cislo % 10;
        sucet += posledna_cifra;
        cislo /= 10;
    }
    return sucet;
}

Úloha

Zázračné platenie fungovalo nasledovne: Nech je skutočná cena nákupu \(c\). Zygro pri zázračnom platení zaplatí \(ciferny\_sucet(c)\) peňazí a teda pri tomto nákupe ušetrí \(n = c-ciferny\_sucet(c)\) peňazí.

Úlohou bolo nájsť každé číslo \(c\), pre ktoré platí, že ak od neho odčítame jeho ciferný súčet, tak dostaneme číslo na vstupe, teda \(n\).

Nech máme zadanú ušetrenú sumu \(n\). Keďže vieme, že každá pôvodná cena \(c\) musela byť aspoň tak veľká ako číslo \(n\), môžeme úlohu riešiť tak, že postupne skúšame všetky čísla \(c \geq n\) a testujeme, či po odčítaní ich ciferného súčtu dostaneme číslo \(n\). Otázkou však zostáva, kedy môžeme prestať skúšať ďalšie, väčšie, čísla \(c\).

Horné ohraničenie na hodnotu \(c\)

Môžeme si všimnúť, že za nákup v hodnote \(c\) môžeme zaplatiť najviac \(9 \cdot len(c)\) peňazí, kde \(len(c)\) je počet cifier čísla \(c\). Vždy teda ušetríme aspoň \(c - 9\cdot len(c)\) peňazí, preto platí nerovnica: \[n \geq c - 9\cdot len(c)\] Z tohto zápisu vieme odvodiť horné ohraničenie pre hodnotu \(c\) \[c \leq n + 9\cdot len(c) \] potrebujeme však odhadnúť \(len(c)\) pomocou \(n\). Na rýchlostnej programátorskej súťaži by sme si zvolili nejakú hodnotu, ktorá by určtite stačila pre nájdenie všetkých možných riešení (napr.: \(len(c) < 2 \cdot len(n)\)). Nezhoršili by sme tak asymptotickú časovú zložitosť a riešenie by sme mali naprogramované rýchlo. Pre úplnosť si ale dokážeme presnejší odhad.

Aká je teda dĺžka čísla \(c\) vzhľadom na dĺžku čísla \(n\)? Ukážeme si, že dĺžky týchto dvoch čísel sa môžu líšiť najviac o jedna.

• Ak je \(c\) jednociferné, po odčítaní ciferného súčtu sa dĺžka výsledku nezmení, \(n\) má teda tiež jednu cifru.
• Ak je \(c\) dvojciferné, \(ciferny\_sucet(c) \leq 18\). Pre všetky čísla \(c \geq 28\) sa po odčítaní \(ciferny\_sucet(c)\) jeho dĺžka nezmení, takže \(n\) bude tiež dvojciferné. No a ak je \(c\) menšie ako 28, výsledné číslo \(n\) bude možno jednociferný (napr. pri číslach 11 až 19).
• Ak je \(c\) \(k\)-ciferné, \(ciferny\_sucet(c) \leq 9k\). Pre všetky \(c \geq 10^{k-1} + 9k\), odčítaním ciferného súčtu jeho dĺžku nezmeníme. Inak môže byť \(n\) len o 1 cifru kratšie. Na skrátenie o dve cifry by totiž muselo platiť, že ciferný súčet je aspoň \(9 \cdot 10^{k-2}\).¹ Dostaneme teda nasledovnú nerovnicu: \(9\cdot 10^{k-2} < ciferny\_sucet(c) \leq 9k\). Táto nerovnica však zjavne nie je splnená pre \(k\) väčšie alebo rovné trom.

Vieme teda, že po odčítaní ciferného súčtu z čísla \(c\) nemôže vzniknúť číslo s počtom cifier zmenšeným o 2. Toto môžeme zapísať ako: \[len(c) - len(n) = len(c)-len(c - ciferny\_sucet(c)) \leq 1\] čím dostávame odhad \(len(c) \leq 1 + len(n)\) a teda spojením týchto dvoch úvah môžeme ohraničiť \(c\) pomocou \(n\): \[c \leq n+9\cdot (1+len(n))\] Posledný krok, ktorý ešte musíme spraviť, je zistenie dĺžky čísla v desiatkovom zápise.

Môžeme použiť funkciu podobnú tej, čo rátala ciferný súčet. Kým je číslo väčšie ako 0, budeme ho deliť 10 a zväčšovať si počítadlo počtu cifier.

Iný spôsob je využiť desiatkový logaritmus. Pre všetky kladné celé čísla platí \(len(n) = \lfloor \log_{10}(n) \rfloor + 1\), kde \(\lfloor n \rfloor\) je dolná celá časť \(n\). Pre 0 pridáme špeciálny prípad, keďže počet cifier čísla nula je 1, čo nesedí s naším vzorčekom. Horná hranica pre \(c\) bude teda \(n + 9 \cdot (\lfloor \log_{10}(n) \rfloor + 2)\).

#include<iostream>
#include<cmath>

using namespace std;

long long ciferny_sucet(long long cislo){
    long long sucet = 0;
    while (cislo > 0) {
        long long posledna_cifra = cislo % 10;
        sucet += posledna_cifra;
        cislo /= 10;
    }
    return sucet;
}

int main() {
    long long z;
    cin>>z;

    for (int i = 0; i<z; ++i) {
        long long n;
        cin>>n;
        long long horna = 10;
        if (n > 0) horna = 9*int(log10(n)+2);
        bool je_riesenie = false;
        for (long long c = n; c <= n+horna; ++c) {
            if (c - ciferny_sucet(c) == n) {
                if (je_riesenie) {
                    cout << " ";
                }
                je_riesenie = true;
                cout << c;
            }
        }
        cout << endl;
    }
    return 0;
}

Zložitosť

Ciferný súčet čísla \(c\) zistíme v čase \(O(\log_{10}(c))\). Avšak, \(c\) a \(n\) má takmer rovnako veľa cifier (\(c\) má nanajvýš o jednu viac), preto je to zároveň čas \(O(\log_{10}(n))\). Pre zadané \(n\) skúšame hodnoty od \(n\) po \(n + 9(\lfloor \log_{10}(n) \rfloor + 2)\), teda dokopy \(9\lfloor \log_{10}(n) + 2 \rfloor\) čísel. To znamená, že vypočítať riešenie pre jedno \(n\) trvá \(O(\log_{10}^2(n))\). No a na vstupe máme \(z\) záznamov, preto je výsledná časová zložitosť \(O(z \cdot \log_{10}^2(n))\).

Pamäťová zložitosť je \(O(1)\), pretože máme iba konštantný počet premenných a výsledky môžeme rovno vypisovať.

Rýchlejšie, matematické riešenie

Na túto úlohu sa ale dá pozrieť aj čisto matematicky. Povedzme, že by mal Zygro zaplatiť sumu \(c\). Toto číslo si môžeme zapísať pomocou jeho cifier ako \[c = 1 \cdot c_0 + 10 \cdot c_1 + 100 \cdot c_2 \ldots \] pričom \(c_i\) je \(i\)-ta cifra čísla \(c\). Koľko je potom \(n = c - ciferny\_sucet(c) \)? Ciferný súčet je len súčet cifier a teda dostávame: \[n = 1 \cdot c_0 + 10 \cdot c_1 + 100 \cdot c_2 \ldots - (c_0 + c_1 + c_2 + \ldots) = (10-1) \cdot c_1 + (100-1) \cdot c_2 \ldots \]

Z tohto čísla potom potrebujeme zrekonštruovať pôvodné \(c\), teda jeho cifry. Vidíme, že \(n\) nám o nultej cifre \(c\) absolútne nič nepovie. To znamená, že posledná cifra \(m\) môže byť ľubovoľná. Ak teda nejaké riešenie existuje, je ich rovno \(10\).

Ďalej potrebujeme nájsť cifry \(c_1, c_2, \ldots c_q\), pre ktoré platí vyššie uvedená rovnosť \(n = (10-1) \cdot c_1 + (100-1) \cdot c_2 + \ldots + (10^q -1) \cdot c_q\), kde \(q\) je počet cifier \(c\), čo vieme, že je najviac počet cifier \(n\) plus jedna.

Algoritmus je potom nasledovný. Zoberieme \(n\) a nájdeme \(q\). Zistíme si celočíselný podiel \(\frac{n}{10^q -1 }\), čím dostaneme \(c_q\). Od \(n\) odčítame \((10^q -1) \cdot c_q\) a zmenšíme \(q\) o jedna. Takto pokračujeme, až kým \(q\) neklesne na nulu, čo nastane po \(O(\log n)\) krokoch.

Posledné, čo musíme skontrolovať, (môžeme to robiť aj počas rátania jednotlivých cifier) je zistiť, či sú nájdené čísla \(c_1, c_2, \ldots c_q\) naozaj cifry – čísla od \(0\) po \(9\). Ak sú všetky naozaj ciframi, zistili sme všetky, okrem nultej, ktorá ale môže byť ľubovoľná. Stačí už len vypísať.

Vhodným udržiavaním si potrebných čísel vieme úlohu pre jedno \(n\) vyriešiť v čase \(O(\log(n))\) s pamäťou \(O(1)\). Celkové riešenie má potom časovú zložitosť \(O(z \log(n))\) a pamäťovú zložitosť \(O(1)\).

O počte cifier a odhade časovej zložitosti

Mnohí z vás radi v riešeniach prehlasovali počet cifier každého \(n\) za konštantu, a teda aj časovú zložitosť za konštantnú.

Odhad časovej zložitosti je veľmi praktická vec. Robíme ho preto, aby sme vedeli približne predpovedať (ešte pred naprogramovaním), ako dlho bude program bežať, keď mu budeme dávať rôzne veľké vstupy. V našej úlohe je \(n\) jedným z dvoch parametrov. Bolo by teda veľmi praktické vedieť, čo sa bude diať keď ho budeme meniť. Preto je odhad \(O(\log n)\) informatívnejší.

Samozrejme, keďže \(n\) mohlo mať najviac 18 cifier, tak to, či \(n=12\) alebo \(n=123456789012345678\) ovplyvní čas behu programu minimálne. Preto môžeme prakticky tvrdiť, že beh programu nezávisí od veľkosti \(n\) (teda, že má program konštantnú časovú zložitosť). Takéto zdôvodnenie ale treba v popise riešenia vždy spomenúť.

Ak by sme úlohu riešili pre veľaciferné čísla, nemohli by sme používať štandartné aritmetické operácie (napr. v C++) alebo by čas výpočtu týchto operácií veľmi závisel od veľkosti čísel (Python, vlastná aritmetika s veľkými číslami). Takýto program by si vyžadoval iné odhady zložitosti.