Zoznam úloh

2. Zázračné platenie

Zadanie

Zygrov dlhoročný sen je navštíviť Švédsko. Dôkladne sa na to pripravuje: študuje históriu, učí sa jazyk[^1] 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]))
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty