Zadanie
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Andrejovi na [email protected]
Táto úloha nadväzuje na úlohu Akútny upgrade z prechádzajúceho kola. Odporúčame si preto aspoň letmo prečítať jej zadanie a aj vzorové riešenie. Na vyriešenie tejto úlohy to síce nie je nutné, myslíme si však, že vám to vie pomôcť.
Timkinmu učiteľovi informatiky sa veľmi páčilo jej vypracovanie domácej úlohy na PRAStarom Kalkulátore. Tak si povedal, že najbližšiu úlohu by mohla celá trieda vypracovať na tomto prastarom počítači. Kedže je ale Timkin kalkulátor jediný zachovaný svojho druhu, dal im najlepší online simulátor PRAStarého Kalkulátora na internete. Jitka sa práve vrátila nevyspatá zo sústredenia a to posledné čo sa jej chce robiť, je riešiť nejaké úlohy.
Úloha
Pomôžte Jitke s jej domácou úlohou a dožičte jej tak zaslúžený spánok.
Podúloha a. (3b)
V rúre sa nachádzajú dve čísla \(a(1\leq a\leq 50000)\) a \(b(0\leq b\leq 1000)\). Vypíšte na výstup jediné číslo \(x\), pričom \(x = a^b\). Inými slovami, vypíšte na výstup \(a\) umocnené na \(b\).
Input:
5 3
Output:
125
\(5^3=5\cdot 5\cdot 5 = 125\).
Podúloha b. (3b)
V rúre sa opať nachádzajú dve čísla \(a, b\) \((1 \leq a, b \leq 10\,000)\). Vypíšte na výstup jediné číslo \(x\), ich najväčší spoločný deliteľ. Pokiaľ vaše riešenie používa príliš veľa krokov, pozrite si priložený link ešte raz :-)
Input:
15 20
Output:
5
5 delí 15 aj 20 bezo zvyšku. Zároveň toto pre žiadne väčšie číslo neplatí.
Podúloha c. (3b)
- (3 bod) V rúre sa nachádza číslo \(x(0\leq x\leq 50000)\) a postupnosť \(n(1\leq n\leq 100)\) kladných čísiel. Na výstup vypíšte jediné číslo \(p\), pričom p je počet čísel v postupnosti, ktoré sú väčšie ako \(x\).
Input:
4 12 5 2 4 8 9 1
Output:
4
Vidíme, že prvé číslo je \(x\) teda \(x=4\). V postupnosti sú potom väčšími číslami čísla 12, 5, 8, 9. Výsledok je teda 4
Podúloha d. (3b)
V rúre sa nachádza postupnosť \(n(1\leq n\leq 100)\) kladných čísel. Je garantované, že niekde v tejto postupnosti sa nachádza jednotka. Určite aspoň raz, možno viackrát. Vašou úlohou je vypísať, na koľkom mieste sa v tejto postupnosti nachádza prvá jednotka.
Input:
5 4 3 9 1 2 55 8 1 3
Output:
5
Jednotka sa v tejto postupnosti nachádza na dvoch miestach, na piatom a deviatom. Na výstup teda vypíšeme prvšiu pozíciu a to 5.
Podúloha e. (3 b)
V rúre sa nachádza postupnosť \(n(1\leq n\leq 100)\) kladných čísel. Na výstup vypíšte túto postupnosť zoradenú od najmenšieho po najväčší.
Input:
1 12 3 4 2
Output:
1 2 3 4 12
Odovzdávanie
Odovzdávanie funguje rovnako ako v predchádzajúcej úlohe. Počas minulého kola malo niekoľko z vás problém s odovzdávaním. V prípade problémov s testovaním, napr. keď testovač testuje váš program dlho, napíšte Andrejovi.
Pred prečítaním tohto vzorového riešenia by ste mali mať isté základy práce v tomto modeli. Veľmi vám môže pomôcť riešenie predchádzajúcej úlohy či jej vzorové riešenie.
Podúloha A
V prípade, že ste poznali alebo vedeli vymyslieť cyklus bola táto úloha pomerne priamočiara. Všetko čo umocňovanie predstavuje je iba viacnásobné násobenie. Stačilo teda použiť jeden pomocný register. Doň vložiť jednotku a potom \(b\)-krát vynásobiť \(a\)-čkom.
get a; get b
put 1; get v
label cyklus
jeq i b koniec
put v; put a; mul; get v
put i; put 1; add; get i
jump cyklus
label koniec
put v; print; stop
Podúloha B
Najväčší spoločný deliteľ dvoch čísel je najväčšie číslo, ktoré delí prvé aj druhé číslo. Jeden spôsob ako ho nájsť je prejsť všetky čísla od \(1\) do \(minimum(a, b)\). Toto riešenie však nemuselo prejsť do potrebného počtu krokov. To, čo sa dá v tomto prípade použiť je Euklidov algoritmus. Pri finálnej implementácií stačí v podstate prepísať pseudokód z wikipédie do nášho PRAStarého Kalkulátora.
label cyklus
get u; get v
jz v koniec
put u; put v; mod; get p;
put v; put p;
jump cyklus
label koniec
put u; print
Podúloha C
Pozornému oku neujde, že čísla na vstupe sú kladné. To pre nás znamená, že môžeme použiť nulu ako zarážku. V prvej fáze prejdeme všetky čísla na vstupe a za každé väčšie ako \(x\), si za nulu pridáme jednu jednotku. Potom je našou úlohou už iba sčítať všetky jednotky, ktoré ostali v rúre. To je úloha, ktorú už z minulého vzorového riešenia dobre poznáme.
get x;
put 0;
label cyklus
get i;
jz i dalej
jgt i x pridaj
jump cyklus
label pridaj
put 1;
jump cyklus
label dalej
label scitaj
get a;
jempty koniec
put a; add
jump scitaj
label koniec
put a
print
Podúloha D
Riešenie tejto podúlohy sa jemne podobná na riešenie predchádzajúcej podúlohy. Na začiatku si potrebujeme do registra vložiť jednotku. To preto aby sme mali s čím jednotlivé čísla porovnávať. To vieme urobiť napr. tak, že si vložíme do rúry nulu a jednotku. Preiterujeme všetky kladné čísla na vstupe, pokým zas nenarazíme na nulu. Potom si napr. do registra j
vložíme jednotku, ktorá ostala na začiatku rúty. Potom prejdeme ešte raz všetky čísla na vstupe a za nulu si vkladáme jednu jednotku za každé číslo na vstupe, ktoré nie je jedna až pokým na jednotku nenarazíme. Potom dočítame čísla, ktoré ostali až pokým znovu nenarazíme na nulu. Potom už máme za nulou iba jednotku za každé číslo, ktoré nebolo jednotka, na ktoré sme narazili pred samotnou prvou jednotkou. Tieto čísla v rúre už stačí len sčítať s čím už máme prax z predchádzajúcej podúlohy. K tomuto súčtu potom nesmieme zabudnúť pripočítať jednotku.
put 0; put 1
label cyklus1
get i
jz i dalej1
put i
jump cyklus1
label dalej1
get j
put 0
label cyklusnajdi
get i
jeq i j cyklusnasiel
put 1
jump cyklusnajdi
label cyklusnasiel
get i;
jz i scitaj
jump cyklusnasiel
label scitaj
get a;
jempty koniec
put a; add
jump scitaj
label koniec
put a; put 1; add; print
Podúloha E
Táto úloha vám mala ukázať, že pomocou PRAStarého Kalkulátora ide robiť aj o čosi zložitejšie veci, ktoré možno poznáte aj zo sveta reálneho programovania. Kedže čísel na vstupe nie je veľa, stačilo si vybrať niektorý z pomalších ale jednoduchších triediacich algoritmov a naimplementovať ho. My sme si vybrali insertion sort. To je triediaci algoritmus, ktorý postupne berie prvky z poľa či listu a vkladá ich do usporiadanej postupnosti. Na začiatku v usporiadanej postupnosti nie je nič. Potom algoritmus postupuje tak, že vezme prvé číslo z neusporiadanej postupnosti a vloží ho na správne miesto do tej usporiadanej. Toto opakuje, pokým neusporiadana postupnosť nie je prázdna. V PRAStarom Kalkulátore bude náš algoritmus vyzerať podobne. V rúre sa budú nachádzať dve postupnosti oddelené 0. Vždy načítame prvé číslo z prvej postupnosti, doiterujeme cez prvú postupnosť, potom prechádzame druhú pričom hľadáme číslu správne miesto. Keď prvý krát stretneme v usporiadanej postupnosti prvok väčší ako naše umiestňované číslo, vložíme najskôr naše číslo a potom pokračujeme ďalej dovkladaním ostatku prvkov z usporiadanej postupnosti. Tento postup opakujeme, pokým nenarazíme pri hľadaní ďalšieho čísla na utriedenie na nulu.
get x; put 0; put x; put 0
label vyberdalsie
get v;
jz v usporiadane
jump prejdi1
label prejdi1
get i;
jz i vlozz
put i
jump prejdi1
label vlozz
put 0
label vloz
get i
jz i specialnevloz2
jgt i v specialnevloz1
put i
jump vloz
label specialnevloz1
put v; put i; jump prejdi2
label specialnevloz2
put v; jump dalej
label prejdi2
get i;
jz i dalej
put i
jump prejdi2
label dalej
put 0
jump vyberdalsie
label usporiadane
jump zbavnuly
label zbavnuly
get i
jz i vypis
put i
jump zbavnuly
label vypis
jempty koniec
print
jump vypis
label koniec
stop
Zdroj
Táto úloha bola pôvodne teoretickým modelom v Olympiáde v Informatike. Pokiaľ Ťa riešenie úloh ako sú v Prasku baví, odporúčame ti riešiť kategóriu B Olympiády v Informatike.
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ť.