Zadanie

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

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)

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