C - Mocnina

Časový limit: 10000000 steps, Pamäťový limit: 10000000 chars

Programovací jazyk: Turing Machine

Počet bodov: 8

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Na páske sú zaradom uložené dve unárne kódované prirodzené čísla X a Y oddelené práve jednou medzerou. Tvojou úlohou je vypočítať funkciu Mocnina(X,Y) = X^Y. Špeciálne platí Mocnina(0,0) = 0⁰ = 1.

Vstup

Páska je ohraničená z ľava. Počiatočný stav je s0. Hlava je nastavená na prvý znak, ktorý je vždy nula. Prvý znak čísla X začína napravo od nej. Naľavo od hlavy už nie je páska. Povolené páskové písmená sú len 0 a 1. Na páske sa nachádzajú práve dve čísla X a Y v unárnom kódovaní oddelené jednou medzerou.

Výstup

Dôležitý je počet jednotiek na páske, ktorý má byť rovnaký, ako hodnota funkcie Mocnina(X,Y). Konečný stav a pozícia hlavy po skončení vykonávania algoritmu nie je podstatná, no nikdy sa nesmie dostať mimo pásku.

Priklad

Vstup:

-t1 -oc
01
0111011111

Výstup:

Vysvetlenie:

Prvé číslo je 2 a druhé 4. Výstup bude teda Mocnina(2,4) = 2⁴ = 16.

Poznámka:

Vo vstupe sú uvedené parametre použité na testovanie pomocou programu palma_ts, môžete ich umiestniť do vstupného súboru. Pozor! Zmenil sa spôsob zápisu Turingovho stroja! Aktuálny spôsob nájdete popísaný v sekcii Dokumenty.

Turing 2010