Zadanie

Zygrov dlhoročný sen je navštíviť Švédsko. Dôkladne sa na to pripravuje: študuje históriu, učí sa jazyk1 a počúva škandinávske pesničky. Popri tom samozrejme pracuje (vo firme “Vysávače a špagety, s.r.o.”), aby si zarobil peniaze na výlet.

Práca je ale náročná, a tak raz večer zaspal nad poviedkami o Pipi Dlhej Pančuche a ocitol sa v zázračnej švédskej dedinke s ešte zázračnejším spôsobom platenia.

Platenie sa líšilo tým, že ak máte za zmrzlinu zaplatiť napríklad \(512\) eur, tak najprv podáte pokladníkovi \(5\) eur, potom \(1\) euro a nakoniec \(2\) eurá (pozor na poradie!). Zygro bol samozrejme veľmi nadšený. Veď na kúpenie zmrzliny mu stačilo iba \(8\) eur, čím ušetril \(504\) eur. Celú noc preto behal po dedinke a zisťoval ceny jednotlivých výrobkov, aby zrátal, koľko peňazí dokáže ušetriť. Aj vo svojom sne je však veľmi unavený, a tak už nezvláda ani obyčajné odčítavanie. Keby tak na to mal program…

Pomôžete mu?

Úloha

Máte dané celé nezáporné číslo \(n\) – cenu výrobku. Vašou úlohou je zistiť, koľko peňazí Zygro ušetrí, ak za výrobok zaplatí vyššie popísaným spôsobom.

Formát vstupu

V prvom riadku vstupu je jediné číslo \(n\) (\(0 \leq n \leq 10^{18}\)) udávajúce cenu. Všimnite si, že \(n\) sa nezmestí do bežnej (32-bitovej) celočíselnej premennej. Pokiaľ programujete v Pascale, odporúčame vám použiť typ int64, v C++ typ long long.

Formát výstupu

Vypíšte jeden riadok, na ktorom bude jediné číslo: množstvo peňazí, ktoré Zygro ušetrí.

Príklady

Input:

512

Output:

504

\(512 - (5 + 1 + 2) = 512 - 8 = 504\)

Input:

1000

Output:

999

\(1000 - (1 + 0 + 0 + 0) = 1000 - 1 = 999\)

  1. Vedeli ste, že švédčina má 2 stredné rody?↩

Úloha je pomerne priamočiara – je potrebné zrátať súčet cifier čísla na vstupe. Ako to spraviť? Na to existuje viacero rôznych prístupov a my si ukážeme dva z nich.

Súčet cifier pomocou celočíselného delenia

Všimnime si, že poslednú cifru čísla \(n\) vieme získať ako zvyšok po delení \(10\) (operátor % v C++ a Pythone, mod v Pascale). Rovnako si všimnime, že celá časť čísla \(n\) po delení \(10\) (operátor / v C++, // v Python a div v Pascale) vyzerá ako pôvodné \(n\), ale bez poslednej cifry. Zopakovaním tohto postupu sa vieme dostať aj ku predposlednej cifre čísla \(n\). A potom k predpredposlednej. A tak ďalej.

Takýmto spôsobom vieme prejsť cez všetky cifry čísla \(n\). Ak ich počas toho budeme aj sčítavať, tak získame náš želaný ciferný súčet – \(digits(n)\).

Časová zložitosť tohto prístupu je úmerná počtu cifier čísla \(n\), čo je zhruba hodnota \(\log n\), preto dostávame zložitosť \(O(\log n)\). Pamäťová zložitosť je konštantná.

#include <iostream>

using namespace std;

long long digits(long long n) {
    long long sum = 0;
    while( n > 0 ) {
        long long last_digit = n % 10;
        sum += last_digit;
        n = n / 10;
    }
    return sum;
}

int main(){
    long long n;
    cin >> n;
    cout << n - digits(n) << endl;
}

Súčet cifier pomocou načítania čísla ako reťazca

Trikovejší spôsob, ako vyriešiť úlohu, je prečítať číslo na vstupe ako reťazec – postupnosť znakov. Potom stačí každý znak skonvertovať na číslo a čísla ščítať. V jazyku Python sa toto robí obzvlášť pohodlne.

n = input()
print(int(n) - sum([int(x) for x in n]))

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