Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu loops_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Denisovi na denis@ksp.sk

Kika sa rozhodla, že napečie palacinky pre celú rodinu. Spravila teda cesto, zapla sporák a zohriala na ňom panvicu. Na neuveriteľne dlhý stôl naukladala neuveriteľne veľa tanierov, pekne vedľa seba ako sa na skúsenu gazdinú patrí, a začala piecť palacinky. Keď bola prvá palacinka upečená, Kika zavolala k svojmu neuveriteľne dlhému stolu celú rodinu a položila palacinku na prvý tanier na stole. Vždy, keď bola ďalšia palacinka hotová, Kika ju položila na prvý tanier na stole.

Keďže Kika dáva palacinky len na prvý tanier, jej rodina musela vymyslieť, ako sa rozdelia. Predsa len, je fajn byť prvý pri stole, ale čo ostatní? Jej rodina si teda vymyslela zaujímavé stravovacie návyky. Ak má niekto na svojom tanieri tri palacinky, tak jednu posunie doprava a ostatné dve zje. Nemôže predsa posunúť ďalej viac palaciniek ako by sám zjedol. Keď Kika dopečie poslednú palacinku, zaujíma ju, koľko palaciniek zostalo každému z rodiny na tanieri.

Úloha

Vašou úlohou je napísať program, ktorý vypíše koľko palaciniek zostalo každému z rodiny na tanieri po tom, ako Kika dopečie poslednú palacinku. Pri stole sa nachádza \(k\) členov rodiny a Kika upečie \(n\) palaciniek. Rodina sa správa podľa týchto stravovacích návykov:

  1. Kika vždy pokladá čerstvo upečenú palacinku na prvý tanier na stole.
  2. Ak má nejaký člen rodiny na tanieri 3 palacinky, tak dve zje a jednu posunie nasledujúcemu členovi rodiny. Kika, ako správna gazdiná, vie odhadnúť, koľko cesta prichystať. Preto posledný človek nikdy nebude musieť posúvať palacinku ďalej.
  3. Ak má akýkoľvek člen rodiny menej ako 3 palacinky, tak nerobí nič.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n\) (\(1 \leq n \leq 10^{15}\)) a \(k\) (\(1 \leq k \leq 40\)). Číslo \(n\) reprezentuje počet palaciniek, ktoré Kika napečie, a \(k\) reprezentuje počet osôb pri stole.

Pri riešení v jazyku C++, Pascal, Java, a podobných, si dávajte pozor na maximálne číslo, ktoré sú schopné celočíselné premenné uložiť. Počet palacieniek môže v posledných troch sadách tieto limity prekročiť. Odporúčame použiť \(64\)-bitové premenné. V jazyku C++ preto namiesto typu int použite typ long long int.

Formát výstupu

Na výstup vypíšte riadok, na ktorom bude \(k\) čísiel, pričom \(k_i\) vyjadruje počet palaciniek, ktoré zostali človeku \(i\) na tanieri po tom, ako Kika dopiekla poslednú palacinku. Tieto čísla vypisujte na výstup bez medzier a za posledným číslom vypíšte znak konca riadku.

Hodnotenie

Vaše riešenie bude testované na 5 rôznych sadách vstupov. Rôzne sady sa budú líšiť špeciálnymi obmedzeniami:

Číslo sady 1 2 3 4 5
maximálne \(n\) \(100\) \(10\,000\) \(10^{12}\) \(10^{15}\) \(10^{15}\)
maximálne \(k\) \(10\) \(15\) \(30\) \(35\) \(40\)

Príklady

Input:

7 4

Output:

1200

Input:

12 5

Output:

01100

Riešenie simuláciou

Prvé dva vstupy boli relatívne malé a na získanie prvých 6 bodov si stačilo poriadne prečítať zadanie a napísať program, ktorý bude palacinku po palacinke aplikovať popísané pravidlá.

Každý tanier si môžeme predstaviť ako jednu premennú, v ktorej si pamätáme, koľko palaciniek sa na ňom aktuálne nachádza. A keďže chceme používať viacero veľmi podobných premenných, uložíme si ich do poľa taniere[]. Palacinky na prvom tanieri budú na pozícii taniere[0], na druhom tanieri na pozícii taniere[1]… Pri položení novej palacinky najprv zvýšime číslo taniere[0]. Následne sa pozrieme, či na tomto tanieri nie sú 3 palacinky. Ak sú, nastavíme túto hodnotu na 0 a 1 pripočítali k taniere[1]. S tanierom na pozícii 1 musíme však opäť spraviť to isté, mohlo sa totiž stať, že sa na ňom zrazu nachádzajú tri palacinky. Pomocou while cyklu teda upravujeme počty palaciniek na tanieroch. V okamihu, keď niektorý z tanierov netreba upravovať sa totiž môžeme zastaviť.

n, k = map(int, input().split())
taniere = [0]*k

for i in range(n):
    taniere[0] += 1
    pozicia = 0
    while taniere[pozicia] == 3:
        taniere[pozicia] = 0
        taniere[pozicia + 1] += 1
        pozicia += 1

print(*taniere, sep='')

Na prvý pohľad by sa nám mohlo zdať, že časová zložitosť takéhoto riešenia je \(O(n^2)\). Pre každú palacinku totiž musíme upraviť prinajhoršom všetkých \(n\) tanierov. V skutočnosti je však táto zložitosť výrazne lepšia. Skúsme sa zamyslieť, koľko palaciniek prejde tanierom každého člena rodiny.

Cez prvú osobu musí prejsť každá palacinka. K druhej osobe sa však dostane iba každá tretia palacinka, to bola totiž situácia, v ktorej človek jedna posunul palacinku človeku dva. Táto vlastnosť však platí všeobecne. Ak som \(i\)-ty človek v rade, tak vždy poslušne počkám, kým mám na tanieri 3 palacinky a až potom pošlem 1 človeku \(i+1\). Tým pádom ale človek \(i+1\) uvidí iba tretinu palaciniek človeka \(i\). Prvý človek ich teda uvidí \(n\), druhý \(\frac{n}{3}\), tretí \(\frac{\frac{n}{3}}{3} = \frac{n}{3^2}\), štvrtý \(\frac{n}{3^3}\) atď.

Každé posunutie palacinky je pritom operácia, ktorú musíme spraviť v našom programe. Celková časová zložitosť takéhoto riešenia je preto:

\[n + \frac{n}{3} + \frac{n}{3^2} + \frac{n}{3^3} + ...\]

Nie je to na prvý pohľad síce jasné, ale súčet takejto postupnosti nikdy neprekročí hodnotu \(2n\). V skutočnosti takýto súčet nikdy neprekročí ani hodnotu \(1.5 \cdot n\). Prečo je tomu tak si nebudeme vysvetľovať, môžete si to však predstaviť tak, že sa snažíte prejsť vzdialenosť \(2n\), ale každý ďalší váš krok je o tretinu menší ako ten predošlý. Nech sa snažíte ako chcete, ku koncu sa približujete príliš pomaly.

Trojková sústava

K riešenie za plný počet bodov je dobré vedieť, čo je to trojková sústava. Ako sa neskôr ukáže, táto znalosť nám vie riešenie celkom značne zjednodušiť.

Trojková sústava je číselná sústava, ktorá zapisuje hodnoty pomocou troch symbolov – 0, 1 a 2. Bežne sme zvyknutí pracovať s číslami v desiatkovej sústave, kde na vyjadrenie rádov používame jednotky, stovky, tisícky atď. čo sú všetko mocniny desiatky. Napríklad číslo \(241_{10}\) vieme zapísať ako \(2 \cdot 10^2 + 4 \cdot 10^1 + 1 \cdot 10^0\).

V trojkovej sústave budeme preto na vyjadrenie rádov používať mocniny trojky. Napríklad zápis čísla \(38_{10}\) by v trojkovej sústave vyzeral ako \(1102_3\), čo opäť vieme zapísať ako \(1 \cdot 3^3 + 1 \cdot 3^2 + 0 \cdot 3^1 + 2 \cdot 3^0 = 38\). V desiatkovej sústave sa číslo prenáša do vyššieho rádu vtedy, ak už dosiahlo desať násobok svojej hodnoty, keďže desať násobok rádu \(10^i\) je vlastne hodnota rádu \(10^{i+1}\). Toto isté platí aj o trojkovej sústave, s tým rozdielom, že číslo prechádza do vyššieho rádu už pri trojnásobku rádu \(i\).

Ako teda vieme trojkovú sústavu využiť pri našom riešení?

Vzorové riešenie

Predstavme si, že v našom zadaní by sme namiesto posúvania palaciniek po troch ich posúvali až v momente, keď by sme ich na tanieri mali 10. Vtedy by nám počty palaciniek na tanieroch tvorili zápis čísla v desiatkovej sústave. Nech je na tanieroch postupne 3, 5 a 1 palacinka. Keďže na najpravejší tanier sa dostane iba každá stá palacinka, to, že sa tam nachádza značí, že sme už museli poposúvať 100 palaciniek. Na druhom mieste je však číslo 5 a na tento tanier sa dostane iba každá desiata palacinka. To znamená, že navyše k tým 100, z ktorých sa jedna dostala na tanier tri a zvyšné boli zjedené sme museli pridať 50 ďalších palaciniek. A číslo 3 na prvom tanieri značí, že navyše ich bolo treba ešte 3. Dokopy sme teda museli poposúvať \(1 \cdot 100 + 5\cdot 10 + 3\cdot 1 = 153\) palaciniek. Navyše si môžeme všimnúť, že pridanie ďalšej palacinky na prvý tanier je rovnaké, ako keby sme k tomuto číslu pripočítali 1.

V našom prípade však neposúvame po desiatich, ale už po troch. Výsledné počty palaciniek teda reprezentujú číslo nie v desiatkovej, ale trojkovej sústave. A pridanie palacinky je rovnako pripočítanie čísla 1. Z toho vyplýva, že ak chceme kde sa po pridaní \(n\) palaciniek nachádza koľko z nich, musíme zistiť, aký je zápis čísla \(n\) v trojkovej sústave.

Prevod do trojkovej sústavy bude vyzerať nasledovne. Ak chceme v desiatkovej sústave vedieť, koľko jednotiek sa v danom čísle nachádza, potrebujeme poznať jeho zvyšok po delení desiatkou. Číslo teda vydelíme, zapamätáme si výsledok delenia a zvyšok. Ak chceme vedieť ďalší rád, výsledok delenia opäť vydelíme a zvyšok nám určí početnosť ďalšieho rádu. Takto postupujeme až kým nedosiahneme nulu ako výsledok delenia. Tento istý postup vieme použiť aj pri prevádzaní čísla do trojkovej sústavy, akurát namiesto delenia 10 budeme deliť 3.

Ako bude teda vyzerať náš program? Na vstupe dostaneme dve čísla \(n\) a \(k\). Ako sme si vyššie popísali, naším cieľom bude previesť číslo \(n\) z desiatkovej sústavy do trojkovej, čo spravíme pomocou postupného delenia a zapisovania si zvyškov. A keďže naše číslo musíme vypísať na \(k\) cifier, pridáme na koniec niekoľko núl.

#include <iostream>
#include <string>

using namespace std;

int main(int argc, const char * argv[]) {
    long long n;
    int k;
    cin >> n >> k;
    
    string vystup = "";
    // pokým je n väčšie ako 0 opakujeme vyššie opísaný proces
    while (n > 0) {
        // zvyšok po delení 3 si rovno zapíšeme do nášho výstupu,
        // preto ho potrebujeme prekonvertovať na string
        vystup += to_string(n % 3);
        n /= 3;
    }
    // Keďže sa môže stať, že nie každému sa pri stole ušli palacinky,
    // pre zvyšok ludí doplníme 0
    while (vystup.size() < k) vystup += "0";

    cout << vystup << "\n";
    return 0;
}

Je tento prístup rýchlejší ako ten predtým? Áno, pretože v každom kroku sa dozvieme počet palaciniek na ďalšom tanieri. To znamená, že nám stačí iba \(k\) krokov, aby sme sa dopracovali k výsledku. Výsledná zložitosť je preto \(O(k)\).

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