Županijsko natjecanje 2016. godine za 3. i 4. razred Srednje Škole - 3. zadatak

Asembler je programski jezik niže razine vrlo blizak strojnom jeziku računala. Pretpostavimo da naš procesor sadrži 10 registara označenih redom s d0, d1, . . . , d9 te razmotrimo jednostavan podskup jezika koji se sastoji od samo dvije naredbe:

add da db Zbrajaju se vrijednosti registara da i db, rezultat se sprema u registar da.

mul da db Množe se vrijednosti registara da i db, rezultat se sprema u registar da.

Neka se na početku izvođenja programa u registru d0 nalazi broj x, a u ostalim registrima nula. U svakom trenutku vrijednost svakog registra ovisi o toj početnoj vrijednosti registra d0 te je možemo opisati matematičkim izrazom ovisnim o varijabli x. Obzirom da u programu samo množimo i zbrajamo, taj matematički izraz mora nužno biti takozvani polinom i to bez slobodnog člana — odnosno izraz oblika:

Zadan je polinom, odredite neki, ne nužno najkraći, program takav da je, na kraju njegovog izvođenja, vrijednost registra d0 određena upravo zadanim polinomom.

Zadani polinom je stupnja najviše 10, a koeficijenti su pozitivni cijeli brojevi manji ili jednaki od 1000. Da bi vaše rješenje dobilo bodove za pojedini test podatak, pronađeni program smije imati najviše 300 naredbi.

ULAZNI PODACI

U prvom redu ulaza nalazi se zapis zadanog polinoma izgrađen prema sljedećim pravilima:

• Zapis polinoma se sastoji od jednog ili više pribrojnika odvojenih znakom “+”. Dakle, zapis je niz znakova oblika “p1+p2+...+pn”.

• Svaki pojedini pribrojnik pi je oblika “axˆk” gdje su koeficijent a i potencija k prirodni brojevi zapisani bez vodećih nula. Između a i k dolaze redom malo slovo ‘x’ te znak potenciranja ‘ˆ’ (ASCII 94, obično AltGr+3 na tipkovnici). Dodatno, vrijede sljedeće iznimke:

– Ako je koeficijent a jednak 1 onda se ispušta.

– Ako je potencija k jednaka 1 onda se ispušta i znak potenciranja “ˆ” i potencija.

• Pribrojnici su poredani od većih potencija prema manjima. Niti jedna dva pribrojnika nemaju istu potenciju.

• Svaka potencija k je prirodni broj manji ili jednak od 10, a svaki koeficijent a je prirodni broj manji ili jednak od 1000.

IZLAZNI PODACI

Ispišite redom naredbe pronađenog programa, svaku u zasebni red. Svaka naredba treba biti točno oblika “add da db” ili “mul da db”, gjde su a i b znamenke. Prije oznake oba registra dolazi jedan znak razmaka.

Napomena: Rješenje ne mora biti jedinstveno.

PRIMJERI TEST PODATAKA

ulaz

5x

izlaz

add d1 d0
add d0 d1
add d0 d1
add d0 d1
add d0 d1

ulaz

8x^3+x^2

izlaz

add d1 d0
mul d1 d0
add d2 d1
mul d2 d0
add d2 d2
add d2 d2
add d2 d2
mul d0 d3
add d0 d2
add d0 d1

ulaz

2x^8+x^4+x

izlaz

add d1 d0
mul d1 d0
mul d1 d1
add d2 d1
mul d2 d1
add d0 d1
add d0 d2
add d0 d2

Objašnjenje

Pojašnjenje drugog primjera: Sljedeća tablica sadrži polinome koji odgovaraju vrijednostima prva četiri registra nakon svake izvedene naredbe u rješenju: