Županijsko natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) - 3. zadatak

Asembler je programski jezik niže razine vrlo blizak strojnom jeziku računala. Naš procesor sadrži 10 registara označenih redom s r0, r1, . . . , r9, a razmatramo jednostavan podskup jezika koji se sastoji od instrukcija oblika “op ra rb rc”. Ova instrukcija primjenjuje operaciju op na vrijednosti registara rb i rc te rezultat operacije sprema u registar ra. Registar ra je cilj, a registri rb i rc izvori u toj instrukciji. Ukoliko instrukcija B dolazi u programu negdje nakon instrukcije A, a barem jedan od izvora u B je jednak cilju u A onda kažemo da B ovisi o A. Primjerice u programu “add r3 r2 r4; add r4 r0 r9; add r5 r2 r3” treća instrukcija koristi kao izvor registar r3 koji je cilj operacije u prvoj instrukciji pa stoga treća instrukcija ovisi o prvoj instrukciji.

Procesor pomoću svog cjevovoda (eng. pipeline) može obrađivati više instrukcija u isto vrijeme što ubrzava izvršavanje programa, ali dovodi do problema s ovisnim instrukcijama. Za naš procesor vrijedi da ako instrukcija B ovisi o instrukciji A onda u programu treba postojati barem 5 instrukcija između instrukcija A i B kako bi program bio ispravan.

Ako program nije ispravan, možemo ga modificirati tako da na proizvoljna mjesta u programu dodamo proizvoljan broj takozvanih NOP instrukcija koje ništa ne rade. Nisu dozvoljene druge modifikacije programa poput brisanja ili mijenjanja redoslijeda instrukcija. Odredite duljinu najkrećeg ispravnog programa koji se na opisani način može dobiti modifikacijom zadanog programa.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 1 000) — broj instrukcija u programu. U j-tom od sljedećih n redova nalaze se redom oznaka registra cilja te oznake dvaju registara izvora u j-toj instrukciji. Oznaka registra je niz od točno dva znaka oblika “rk” (bez razmaka) gdje je k znamenka između 0 i 9. Oznake registara su odvojene točno jednim razmakom.

Izlazni podaci

U prvi red ispišite traženu najmanju duljinu programa.

Primjeri test​ podataka

Ulaz

3
r3 r2 r4
r4 r0 r9
r5 r3 r2

Izlaz

7

Ulaz

7
r0 r0 r0
r0 r1 r2
r1 r2 r3
r3 r2 r3
r2 r2 r2
r0 r0 r0
r1 r9 r8

Izlaz

9

Ulaz

7
r5 r4 r6
r3 r1 r2
r4 r5 r6
r9 r3 r2
r4 r5 r6
r9 r9 r3
r1 r5 r6

Izlaz

15

Objašnjenje

Treća instrukcija ovisi o samo prvoj, dok prva i druga instrukcija ne ovise o ničemu. Jedan najkraći ispravni program dobijemo umetanjem 4 NOP instrukcije prije treće instrukcije: “add r3 r2 r4; add r4 r0 r9; NOP; NOP; NOP; NOP; add r5 r2 r3”.