8. Oprášený startup

V dávnych časoch, na ktoré sa v KSP pamätá už len Mišof, sa snažil Dávidko¹ rozbehnúť start-up so špeciálnymi ‘Dávidkovými procesormi’. V tom čase predstavovali so svojou 32 bitovou výpočtovou jednotkou a takmer 77 MB pamäťou vrchol technického pokroku. Bohužiaľ, kvôli slabej mediálnej kampani neboli tieto procesory úspešné a celý Dávidkov projekt zapadol prachom.

Nedávno, prehrabávajúc sa zákutiami T2, objavil tento projekt Syseľ a povedal si, že teraz by už mohol dopadnúť lepšie. Ísť však na trh s procesorom by nebolo príliš rozumné. Ak by však daný procesor upravil tak, aby vedel komprimovať text, tak by ‘Sysľov komprimátor’ mohol zožať nečakaný úspech. Akurát tá úprava nie je taká jednoduchá, keďže ‘Dávidkov procesor’ beží na veľmi starom a primitívnom systéme. Vy si s tým však určite nejak poradíte.

Dávidkov procesor

Dávidkov procesor obsahuje jeden zásobník (stack), s ktorým pracujú dané inštrukcie. Na zásobník sa ukladajú 32-bitové čísla so znamienkom, teda čísla z rozsahu \(-2^{31}\) až \(2^{31}-1\). Na začiatku behu programu je zásobník prázdny.

Zásobník zapisujeme horizontálne, pričom napravo sa nachádza vrch zásobníka. Reťazec "..." reprezentuje pôvodný stav zásobníka. Reťazec "...|a|b" značí, že na vrchu zásobníka sa nachádza číslo \(b\) a pod ním číslo \(a\). Hodnota "S[n]" je \(n\)-tá hodnota zásobníka. Ak je \(n\geq 0\) táto hodnota sa počíta od spodku, ak \(n<0\), tak od vrchu.

Dávidkov procesor pozná nasledovné príkazy:

Ak by pri vykonávaní niektorého príkazu nebolo v zásobníku dostatočné množstvo čísel (napríklad aspoň 2 pre JGZ, aspoň 1 pre OUT), program skončí chybou. Program tiež skončí chybou, ak je na zásobníku v niektorom momente viac ako \(20\,000\,000\) čísel, alebo sa vykoná viac ako \(300\,000\,000\) príkazov.

Technické detaily aritmetických operácií (pretečenie, modulo zo záporného čísla atď.) fungujú rovnako ako v C++.

Program si po spustení udržiava hodnotu \(prikaz\), ktorá ukazuje na príkaz, ktorý sa aktuálne vykonáva. Táto hodnota je na začiatku 0 (začína sa prvým príkazom). Hodnota \(prikaz\) sa zvýši o 1 po dokončení aktuálneho príkazu. Ak nastal skok príkazom "JGZ", táto premenná sa ešte predtým zmení o danú veľkosť skoku \(b\), následne sa však opäť posunie o 1 dopredu. Ak teda \(b=-1\), tak \(prikaz\) bude ukazovať opäť na ten istý príkaz. V okamihu ako premenná \(prikaz\) ukazuje mimo existujúce príkazy, program je považovaný za korektne zastavený.

Úloha

Dávidkov procesor podporuje iba uvedenú malú sadu príkazov. Vašou úlohou je pomocou týchto príkazov napísať čo najkratší program, ktorý vypíše zadaný text.

Formát vstupu

Dostanete 9 rôznych súborov s textami, všetky používajú štandardnú 7-bitovú ASCII reprezentáciu znakov. Niektoré z textov sú zmysluplné anglické alebo slovenské texty, iné sú vytvorené umelo. Súbory so vstupmi majú názvy 1.in, 2.in, … , 9.in.

Formát výstupu

Odovzdajte jeden ZIP archív, ktorý bude obsahovať súbory s názvami 1.out, 2.out, … , 9.out. Pre každý vstupný text teda odovzdávate samostatný súbor s programom pre Dávidkov procesor.

Každý súbor sa musí skladať z príkazov popísaných vyššie a vypísať daný text. Odovzdaný program je zoznam inštrukcií, každá na samostatnom riadku. Inštrukcie píšte veľkými písmenami presne ako sú udané v tabuľke.

Uvedomte si, že vašou úlohou je vypísať presne taký istý text, vrátane znakov ako medzery alebo konce riadkov. Prvé 4 vstupy neobsahujú znak konca riadka.

Hodnotenie

Každý z deviatich textov bude hodnotený samostatne. Za vyriešenie každého z nich sa dá získať nejaká časť bodov a výsledný bodový zisk je súčet bodov za každý text.

V tejto úlohe budete súťažiť proti sebe. Bodovanie v rámci jedného textu je škálované podľa najlepšieho odovzdaného riešenia.

Skóre odovzdaného programu sa vypočíta ako počet inštrukcií použitých v programe (teda počet príkazov v zdrojovom kóde, nie počet príkazov, ktoré sa naozaj vykonajú počas behu programu), pričom príkaz "PUSH" sa počíta za 2. Nech \(O\) je skóre programu, ktorý ste odovzdali, \(M\) je najmenšie dosiaľ získané skóre nejakého programu (vrátane toho so skóre \(O\)) a \(B\) je počet bodov, ktoré sa dajú získať za vyriešenie daného textu. Výsledného skóre tohto programu je \(B\cdot \frac{M}{O}\).

Počas behu kola budeme hodnoty \(M\) (najmenšie dosiahnuté skóre pre každý text) aktualizovať približne raz za týždeň a po skončení kola ich aktualizujeme znova a vypočítame finálne body.

Keďže neodovzdávate programy a nás zaujíma, ako úlohu riešite, môžete do ZIPka priložiť aj zdrojové kódy programov, ktoré ste pri riešení použili, prípadne stručný popis, ak by ste sa chceli pochváliť.

Súbory na stiahnutie

Na tomto odkaze: http://media.ksp.sk/ulohy/34rocnik/1kolo/prikl8-na-stiahnutie.zip si viete stiahnuť niekoľko užitočných súborov. Je tam spomínaných deväť textov, pre ktoré máte vytvoriť programy a takisto C++ program, ktorý simuluje tento zásobníkový procesor. Vďaka nemu si viete otestovať, či vami vytvorený program naozaj vypíše žiadaný text. Rovnakým spôsobom budeme tiež simulovať vaše riešenia na testovači, takže si môžete overiť implementáciu dôležitých častí zásobníkového procesora.

Príklad

Input:

Hello

Output:

PUSH 72
OUT
PUSH 203
PUSH 2
DIV
PUSH 2
JGZ
PUSH 80
OUT
OUT
PUSH 108
PUSH 111
PUSH 0
PUSH 0
READ
OUT
READ
OUT
OUT

Všimnite si, že príkazy na riadkoch 7 a 8 (číslujeme od 0) boli preskočené vďaka "JGZ" a nikdy sa nevykonali. Program skončil korektne a na zásobníku ostalo číslo 108. Skóre takéhoto programu je 28.