4. Sladká odmena vzorové riešenie

7 4

1200

12 5

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)\).