Zadanie

Kamila má rada kávu. Rokmi pokusov zistila presný objem kávy, pri ktorom sa jej pracuje najlepšie. Dnes sa dozvedela, že má náročnú domácu úlohu, ktorú treba rýchlo odovzdať, a potrebuje sa posilniť. Zamierila teda ku svojej zbierke výberových káv. Kávy v zbierke sú uskladnené v rôzne veľkých vrecúškach: každé vrecúško je dvakrát väčšie ako to pred ním, počínajúc vrecúškom s hmotnosťou 1 gram. To znamená, že v zbierke má vrecúška s váhami \(1, 2, 4, 8, \dots, 2^n\) gramov. Ako v každej správnej zbierke, aj v tej Kamilinej je vrecúško každej veľkosti práve raz.

Ktoré vrecúčka má Kamila vybrať aby dosiahla svoju vytúženú hladinu kofeínu?

Úloha

Na vstupe dostanete \(n\) – potrebnú hmotnosť kávy a máte zistiť, ktoré z vrecúšok má Kamila zobrať, ak chce mať presne \(n\) gramov kávy.

Formát vstupu

Vstup má jeden riadok a v ňom jedno celé číslo \(n\). Môžte predpokladať, že \(1 \leq n \leq 10^{18}\).

Upozornenie

Dajte si pozor na to, že váš program musí pracovať aj s hodnotami, ktoré sa nezmestia do bežnej (32-bitovej) celočíselnej premennej. Na ich uloženie potrebujete použiť premennú s dostatočne veľkým rozsahom – napríklad int64 v Pascale alebo long long v C++.

Takisto si dajte pozor, že súčin dvoch 32-bitových premenných vráti 32-bitové číslo bez ohľadu na to, či sa tam výsledok zmestí. T.j. x := 1000000 * 1000000 uloží do x hodnotu 1420103680 bez ohľadu na to, či x je int64 alebo longint.

Formát výstupu

Vypíšte jediný riadok a v ňom použité vrecúška oddelené medzerou v poradí od najmenšieho po najväčšie.

Nezabudnite ukončiť riadok znakom konca riadku. Teda napríklad v Pascale vypíšte výsledok volaním writeln(vysledok), v C++ zase volaním cout << vysledok << endl.

Príklad

Input:

20

Output:

4 16

Input:

35

Output:

1 2 32

Úloha sa dá riešiť dvoma spôbmi, buď vrecúška prechádzame od najmenších po najväčšie alebo naopak. Formát výstupu (tam vypisujeme čísla od najmenších) nám napovedá, ktorý spôsob bude asi jednoduchší.

Celý algoritmus je veľmi jednoduchý – ak je celková hmotnosť nepárna, musíme použiť vrecúško s hmotnosťou \(1\), ak je hmotnosť párna tak vrecúško použiť nesmieme. Po prípadnom odčítaní najmenšieho vrecúška nám ostalo párne číslo a tiež hmotnosti všetkých ostatných vrecúšok sú párne. Preto môžeme imaginárne zmenšiť všetky hmotnosti na polovicu a zrazu riešime tú istú úlohu len s menšími číslami.

Algoritmus bude teda opakovane kontrolovať paritu čísla zo vstupu. Keď je číslo v \(i\)-tom kole nepárne, vypíše hmotnosť \(i\)-teho vrecúška a po každej kontrole vydelí číslo zo vstupu dvoma.

Koľkokrát môžeme vydeliť číslo \(n\) dvoma, kým dostaneme jednotku? Správna odpoveď je \(\log_2(n)\) (dvojkový logaritmus z \(n\)), pretože \(\log_a(a^x) = x\)1. Preto algoritmus skončí po \(O(\log n)\) krokoch. Časová zložitosť je teda \(O(\log n)\) a pamäťová \(O(1)\), pretože si stačí pamätať zopár čísel.

Všimnime si, že každé prirodzené číslo sa dá zapísať ako súčet rôznych mocnín dvojek. Tento rozklad je skoro to isté ako prevod čísla do dvojkovej (binárej) sústavy.

var hmotnost,mocnina : int64;
    treba_medzeru : boolean;
begin
    treba_medzeru := false;
    mocnina := 1;
    readln(hmotnost);
    while hmotnost > 0 do begin
        if hmotnost mod 2 = 1 then begin 
            if treba_medzeru then write(' ')
            else treba_medzeru := true;
            write(mocnina);
        end;
        hmotnost := hmotnost div 2;
        mocnina := mocnina * 2;
    end;
    writeln;
end.
#include <iostream>
using namespace std;

int main(){
    bool treba_medzeru = false;
    long long mocnina = 1;
    long long hmotnost;
    cin >> hmotnost;
    
    while(hmotnost > 0) {
        if (hmotnost % 2) {
            if (treba_medzeru) cout << " ";
            else treba_medzeru = true;
            cout << mocnina;
        }
        hmotnost /= 2;
        mocnina *= 2;
    }

    cout << endl;
}
n = int(input())
x = 1
ans = [] # pre jednoduchší kód sa uspokojíme s horšou pamäťovou zložitosťou
while n > 0:
    if n%2: ans.append(str(x))
    x *= 2
    n //= 2
print(' '.join(ans))

  1. Logaritmus \(n\) pri základe \(a\) zapisovaný ako \(\log_a(n)\) má nasledovný význam: číslo, na ktoré musíme umocniť \(a\), aby sme dostali hodnotu \(n\). Preto \(\log_2(8)=3\) a \(\log_{10}(100)=2\). No a to, čo používame, je vzťah \(a^{\log_a(n)}=n\). Inými slovami, ak umocníme číslo \(a\) na číslo, na ktoré musíme umocniť \(a\) aby sme dostali \(n\), dostaneme \(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ť.