Županijsko natjecanje iz informatike 2016. / Prva podskupina (1. i 2. razred) - 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 s varijablom \(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: \[a_nx^n+a_{n−1}x^{n−1}+...+a_2x^2+a_1x\]

Za zadani program, odredite zapis polinoma koji opisuje vrijednost registra d0 nakon izvođenja programa. Zapis polinoma definiramo na sljedeći način:

• Zapis polinoma se sastoji od jednog ili više pribrojnika odvojenih znakom +. Dakle, zapis je nizznakova oblika \(p_1+p_2+...+p_n\).

• Svaki pojedini pribrojnik pije 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 istupotenciju.Primijetite da a ne može biti nula jer potencije koje se ne pojavljuju u polinomu ne sudjeluju u zapisu, a k ne može biti nula jer u ovom zadatku polinomi nikada nemaju slobodni član.

Test podaci su takvi da se rezultat svake operacije u programu može opisati polinomom s potencijamamanjim ili jednakim od \(100\) te koeficijentima manjim od \(231\).

Ulazni​ podaci

U prvom redu nalazi se broj prirodni \(n\) \((n \leq 100 )\) broj naredbi. U svakom od sljedećih n redova nalazise jedna naredba programa. Svaka naredba je ili add da db ili mul da db, gjde su \(a\) i \(b\) znamenke. Prije oznake oba registra dolazi točno jedan znak razmaka.

Izlazni podaci

U prvi red potrebno je ispisati niz znakova – zapis traženog polinoma kako je opisano u tekstu zadatka.

Bodovanje

• U test podacima vrijednim \(20 \%\) bodova pojavljuju se samo add naredbe.

Primjeri test​ podataka

Ulaz

5
add d1 d0
add d0 d1
add d0 d1
add d0 d1
add d0 d1

Izlaz

5x

Ulaz

10
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

Izlaz

8x^3+x^2

Ulaz

10
add d1 d0
add d2 d0
mul d1 d0
add d9 d1
mul d9 d1
add d0 d1
add d0 d9
add d0 d9
mul d0 d0
add d0 d2

Izlaz

4x^8+4x^6+4x^5+x^4+2x^3+x^2+x