Zoznam úloh

1. Kupujeme RAMky

Zadanie

V tejto nezvyčajnej a neistej dobe si Andrej založil nový biznis — obchoduje s RAMkou na spotovom trhu. Kvôli KSP1 sú však dnes ceny RAMiek veľmi nepredvídateľné… ba čo viac, už aj kapacity modulov.

Obchodníci totiž začali kapacitu udávať v nových jednotkách s cieľom zmiasť konkurenciu a teraz nevieme, či modul s kapacitou 16 mega kilo mikro centi bajtov je výhodnejší ako rovnaký modul s kapacitou 8 kilo deka bajt mili deci bajtov.

Pomôžte Andrejovi zorientovať sa v jednotkách.

Úloha

Vašou úlohou je premieňať nové jednotky na bajty. Jednotka sa skladá z neprázdnej postupnosti písmen reprezentujúcich prípony SI z nasledovnej množiny2:

Názov Skratka Hodnota Mocnina 10
mega M $1\,000\,000$ $10^6$
kilo k $1\,000$ $10^3$
hekto h $100$ $10^2$
bajt B $1$ $10^0$
centi c $0.01$ $10^{-2}$
milli m $0.001$ $10^{-3}$
mikro u $0.000\,001$ $10^{-6}$

Hodnotu jednotky dostaneme tak, že spolu postupne násobíme a delíme všetky prípony v jej zápise. Hodnotou prvej prípony sa výsledok vždy násobí. Takisto každá prípona, ktorá nie je menšia než predchádzajúca, násobí výsledok svojou hodnotou. Pokiaľ však ľubovoľnej prípone predchádzala prípona ostro väčšia, novou príponou sa namiesto násobenia delí.

Andrej vám poslal zopár príkladov pre lepšie pochopenie:

  • kilo bajt $= 1\,000 / 1 = 1\,000$
  • bajt kilo $= 1 \cdot 1\,000 = 1\,000$
  • milli centi $= 0.001 \cdot 0.01 = 0.00001$
  • kilo kilo bajt $= 1\,000 \cdot 1\,000 / 1 = 1\,000\,000$
  • mega kilo hekto bajt centi milli $= 1\,000\,000 / 1\,000 / 100 / 1 / 0.01 / 0.001 = 1\,000\,000$

Formát vstupu

V prvom riadku je reťazec dĺžky $n$ $(1 \leq n \leq 10^6)$, ktorý pozostáva zo skratiek prípon.

Úloha má dve sady, za vyriešenie každej dostanete štyri body. V prvej sade platí, že $n \leq 10$ a žiadny medzivýsledok výpočtu ani celkový výsledok nie je menší než $1$ ani väčší než $10^5$.

Formát výstupu

Vypíšte jeden riadok a v ňom jedno číslo – výslednú hodnotu zápisu v bajtoch.

Príklady

Vstup

kB

Výstup

1000

kilo je menšia prípona ako bajt, teda výsledok je $1\,000 \cdot 1 = 1\,000$.

Vstup

khBcmu

Výstup

1000000000000

Jednotky sú klesajúce, takže všetkými okrem prvej delime, teda výsledok je $1\,000 / 100 / 1 / 0.01 / 0.001 / 0.000\,001 = 1\,000\,000\,000\,000$


  1. Kríza Stratenej Pamäte ↩

  2. Všimnite si, že pre účely úlohy považujeme aj slovo bajt za príponu s významom $1$. ↩

Riešenie s násobením/delením medzivýsledku za 4 body

Budeme prechádzať postupnosť skratiek prípon zľava doprava. Spočiatku vynásobíme/vydelíme hodnoty prvých 2 prípon. Ich výsledok si zapamätáme a následne ho vynásobime/vydelíme ďalšou hodnotou prípony. Takto pokračujeme až na koniec postupnosti.

To, či násobime, alebo delíme, možno nájsť v zadaní. Ak nasledujúca prípona nie je menšia, násobime, inak delíme.

Na vstupe dostávame len skratky prípon, my potrebujeme tieto skratky prípon premeniť na ich hodnotu. Na to si môžeme vytvoriť slovník, kde kľúč bude skratka prípony a hodnota bude hodnota prípony. Teda, ak potrebujeme poznať hodnotu ľubovolnej skratky, stači sa v slovníku pozrieť, aká hodnota je skratke priradená.

Postupnosť skratiek prechádzame raz, teda časová zložitosť je $O(n)$, kde $n$ je počet skratiek na vstupe. Pamäťová zložitosť je tiež $O(n)$, pamätáme si všetky skratky zo vstupu.

Nevýhody tohto riešenia

Prístup s násobedním/delením medzivýsledku prináša nasledujúce komplikácie:

  1. V niektorých prípadoch bude algoritmus pracovať s float hodnotami, teda desatinnými číslami. Tie sú uložené v binárnej sústave a existujú také, ktoré sa nedajú zapísať konečným počtom bitov, teda majú nekonečný bitový rozvoj (podobne ako môžu mať desatinné čísla nekonečný desatinný rozvoj). Zároveň máme len konečný počet bitov, ktoré môžeme použiť na reprezentáciu daného desatinného číslo. Teda nekonečný bitový rozvoj nevieme zapísať konečným počtom bitov, z čoho vyplýva, že číslo musíme zaokrúhliť, a teda bude nepresné.
    Pri kumulácii takýchto nepresností a následnými operáciami s nepresnými číslami, násobeniami/deleniami, sa bude zaokrúhlovacia chyba zväčšovať, čo nám na konci môže dať nesprávny výsledok.
    Všeobecne je dobré sa vyhnúť práci s float hodnotami, ak sa to dá.

  2. Môže nastať prípad, keď násobíme veľa veľkých čísel za sebou, to napríklad, keď vstup bude tvorený iba z prípon mega. Potom výsledok nebudeme vedieť reprezentovať, keďže bude obrovský. V Pythone sa zaokrúhli na nekonečno a v C++ nastane tzv. overflow, teda pretečenie.

  3. Môže nastať prípad, keď násobíme veľa malých desatinných čísel, to napríklad, keď vstup bude tvorený iba z prípon mikro. Tentokrát bude výsledok hrozne malé číslo, opäť nebude reprezentovateľné. V Python by sa číslo zaokrúhlilo na 0 a v C++ by nastal tzv. underflow, teda podtečenie.

V prvej sade tieto problémy ešte nemusíme riešiť, keďže $n \leq 10$ a zároveň platí, že medzivýsledok je vždy medzi $1$ a $10^5$. Teda nerobíme veľa operácii, zaokrúhlovacie chyby sa neprejavia a výsledok nebude nikdy obrovský, ani príliš malé desatinné číslo. Existuje aj riešenie za 4 body, ktoré vôbec nepoužíva floats, viď odstavec s názvom Integer-only riešenie za 4 body.

postupnost = input()
n = len(postupnost) # zistíme veľkost reťazca, teda počet skratiek

# vytvoríme si slovník so skratkami a ich hodnotami, takto vieme ľahko zistiť hodnotu ľubovolnej zo skratiek
# ak chceme vypísať hodnotu skratky "M", stačí použiť príkaz: print(skratky["M"])
skratky = {"M":1_000_000, "k": 1_000, "h":100, "B":1, "c":0.01, "m":0.001, "u":0.000001} 

# pozrieme sa na prvú skratku a uložíme si ju ako predošlú skratku
predosla_skratka = postupnost[0]

# do premennej výsledok si uložíme hodnotu prvej skratky
vysledok = skratky[predosla_skratka]

# vo for loope prechádzame až od druhej skratky 
# prechádzajúcu skratku vždy poznáme, keďže ju máme uloženú v premennej predosla_skratka
for i in range(1, n):
    nova_skratka = postupnost[i] # uložime si do premennej novú skratku

    # porovnáme hodnotu predošlej a novej skratky, podľa ich veľkosti buď násobíme alebo delíme
    if (skratky[predosla_skratka] <= skratky[nova_skratka]): 
        vysledok *= skratky[nova_skratka]
    else:
        vysledok /= skratky[nova_skratka]

    predosla_skratka = nova_skratka # skratka, ktorá je teraz nová, bude v ďalšej iteráci for loopu už predošlá

# nakoniec vypíšeme výsledok, ak je menší ako 1, bude to desatinné číslo
# ak je väčší alebo rovný 1, chceme ho zaokrúhliť na celé číslo, čo spraví int(vysledok)
print(vysledok if vysledok < 1 else int(vysledok))

Integer-only riešenie za 4 body

V prvom riešení sa nám mohlo stať, že sme násobili alebo delili desatinným číslom, z čoho nám vznikol float. Napr. v Pythone, ak vynásobime $1000 * 0.1$, dostaneme číslo $100.0$, čo je typu float.

Existuje trik, akým sa vieme úplne vyhnúť počítaniu s desatinnými číslami, teda aj ich zaokruhlovacím chybám.

Začneme s tým, že chceme, aby všetky hodnoty skratiek boli celé čísla. To môžeme spraviť tak, že každú z nich vynásobíme číslom $1\,000\,000$. Teda napríklad prípona mikro, ktorá má hodnotu $0.000\,001$, jej nová hodnota bude $1$.

Ďalej budeme pokračovať ako v predošlom riešení, budeme si držať nejaký medzivýsledok, ktorý budeme násobiť/deliť novými hodnotami skratiek. Toto by nám samozrejme dávalo nesprávne výsledky, keďže každá z hodnôt je $1\,000\,000$-krát väčšia.

Stačí však po každom násobení vydeliť medzivýsledok hodnotou $1\,000\,000$. Takto bude výsledok správny, keďže najprv sme hodnotu skratky vynásobili $1\,000\,000$, ale nakoniec sme medzivýsledok vydelili tou istou hodnotou. Zároveň, sme pri tom nepoužili floaty. Dôležité je medzivýsledok najprv vynásobiť hodnotou skratky, až potom vydeliť $1\,000\,000$. Ak by sme to spravili naopak, hrozí, že medzivýsledok sa zaokrúhli na nulu.

Podobne pre delenie, tu budeme musieť pred každým delením vynásobiť medzivýsledok hodnotou $1\,000\,000$. Znova, medzivýsledok bude správny, opäť je však dôležité poradie operácii, v tomto prípade najprv násobime.

Toto riešenie funguje iba v prvej sade, keďže v 2. sade môže byť medzivýsledok ľubovoľne veľký. Oproti riešeniu s floatmi však dokáže fungovať aj na príklady s medzivýsledkami až po približne $10^{18}$, pokiaľ použijeme 64-bitové čísla (na rozdiel od floatov, ktoré majú iba 23 bitov presnosti). Celé čísla v Pythone majú presnosť efektívne nekonečnú, čím sú však väčšie, tým je práca s nimi pomalšia… A najmä, tento prístup nám nedovoľuje reprezentovať výsledky menšie než $1$.

Lepšie riešenie s počítaním exponentu za 8 bodov

V tomto riešení opäť prechádzame postupnosť skratiek zľava doprava, rozdiel je v tom ako si pamätáme medzivýsledok. Čo si môžeme všimnúť je, že hodnoty všetkých skratiek sú mocniny čísla 10. Teda každé z nich vieme zapísať ako $10^x$, kde $x$ je nejaké celé číslo. Napr. $100$ sa dá zapísať ako $10^2$ alebo $0.01$ ako $10^{-2}$.

Zároveň platí vzťah pre násobenie $10^a * 10^b = 10^{a+b}$, podobne pre delenie $10^a / 10^b = 10^{a-b}$, kde $a, b$ sú celé čísla. Z toho vyplýva, že aj po vynásobení a vydelení hodnôt skratiek sa bude exponent dať zapísať ako $10^x$, kde $x$ je celé číslo.

Miesto násobenia a delenia hodnôt si teda budeme pamätať, akú má hodnotu exponent, teda náš medzivýsledok bude hodnota exponentu. Spočiatku to bude exponent prvej skratky. Postupne k nemu pričítavame exponenty ďalších skratiek, to v prípade, ak by sme mali násobiť medzivýsledok hodnotou ďalšej skratky, inak od neho odčítavame exponent, teda keď by sa malo deliť.

Na konci máme exponent, podľa ktorého poznáme aj aký ma byť správny výstup.

Tu sa časová ani pamäťová zložitosť nezmení, keďže stále prechádzame celú postupnosť. Môžeme si rozmyslieť aj to, že sa lepšia časová zložitosť v tejto úlohe ani nedá dosiahnuť, keďže na každú skratku sa určite budeme musieť pozrieť aspoň raz, aby sme úlohu korektne vyriešili.

Pamäťovú zložitosť vieme optimalizovať, viď odstavec s názvom Optimalizácia pamäťovej zložitosti.

Výpis výstupu čísla s exponentom

Na konci dostaneme exponent čísla, ktoré má byť výstupom úlohy. Teda ak dostaneme exponent rovný 3, tak výstup má byť $10^3$. Tento exponent by mohol byť veľmi veľký, preto nechceme vypísať hodnotu vo forme print(10**exponent), keďže by sa najprv vyhodnotil výraz 10**exponent, ten by však mohol byť taký veľký, že sa zaokrúhli na nekonečno a to sa vypíše. Alebo naopak taký malý, že sa zaokrúhli na 0 a to sa vypíše.

Miesto toho vieme vypísať výstup nasledovne.

Ak je exponent kladný, potom číslo začína s 1 a pokračuje s počtom núl, aký veľký je exponent. Teda nevyhodocujeme výraz, len vypíšeme číslicu 1 a za to počet núl, aký veľky je exponent.

Podobne, ak je exponent záporný, číslo je desatinné, začína s nulou a desatinnou čiarkou, pokračuje s počtom núl, aký veľky je exponent - 1 a je zakončený číslicou 1. Opäť miesto vyhodnotenia výrazu vypisujeme ako “vyzerá” to desatinné čislo.

postupnost = input()
n = len(postupnost) # zistíme veľkost reťazca, teda počet skratiek

# vytvoríme si slovník so skratkami a ich exponentmi so základom 10, takto vieme ľahko zistiť exponent ľubovolnej zo skratiek
# ak chceme vypísať exponent skratky "M", stačí použiť príkaz: print(skratky["M"])
skratky = {"M":6, "k": 3, "h":2, "B":0, "c":-2, "m":-3, "u":-6} 

# pozrieme sa na prvú skratku a uložíme si ju ako predošlú skratku
predosla_skratka = postupnost[0]

# do premennej výsledok si uložíme exponent prvej skratky
exp = skratky[predosla_skratka]

# vo for loope prechádzame až od druhej skratky 
# prechádzajúcu skratku vždy poznáme, keďže ju máme uloženú v premennej predosla_skratka
for i in range(1, n):
    nova_skratka = postupnost[i] # uložime si do premennej novú skratku

    # porovnáme hodnotu predošlej a novej skratky, podľa ich veľkosti buď pričítavame alebo odčítavame exponent
    if (skratky[predosla_skratka] <= skratky[nova_skratka]): 
        exp += skratky[nova_skratka]
    else:
        exp -= skratky[nova_skratka]

    predosla_skratka = nova_skratka # skratka, ktorá je teraz nová, bude v ďalšej iteráci for loopu už predošlá

# podľa exponentu zistíme, či je to desatinné čislo alebo celé číslo
# ak je menší ako 0, je to desatinné číslo, inak je to celé číslo
if exp < 0:
    # takto vypíšeme desatinné číslo, skladá sa z "0.", potom nasleduje (-exp - 1) núl a nakoniec čislica "1"
    print("0." + (-exp - 1) * "0" + "1")
else:
    # takto vypíšeme mocninu 10, keď exponent je kladný
    print("1" + exp*"0")

Optimalizácia pamäťovej zložitosti

Môžeme si všimnúť aj to, že postupnosť skratiek nemusíme mať celú uloženú v pamäti. To preto, lebo porovnávame vždy 2 skratky vedľa seba, stačí si pamätať v každom momente len tie 2. Pamäťovú zložitosť teda vieme optimalizovať na konštantnú.

Slovník má tiež konštantnú pamäť, keďže obsahuje konštantný počet prípon zo zadania.

Zároveň v tomto prípade musíme prispôsobiť aj vypisovanie výstupu. V predošlej ukážke ho vypisujeme s využitím lineárne veľkej pamäťovej zložitosti. Pri zavolaní napr. print("1" + exp * "0") sa najprv vyhodnotí výraz vo vnútri funkcie. Tento výraz môže byť však lineárne veľký vzhľadom k $n$, teda $O(n)$ pamäti.

Vypisovanie výstupu vieme tiež optimalizovať na konštantnú pamäťovú zložitosť. Podobne ako sme načítavali vstup po jednom znaku, tu budeme vypisovať výstup po jednom znaku.

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