Državno natjecanje 2014. godine za 3. i 4. razred Srednje Škole - 1. zadatak - 2. dan

Goran nije stigao smisliti zadatak za natjecanje jer je zadnjih par dana proveo zabavljajući se najboljom igrom ikada. Nadam se da nemate planove za sljedećih par sati jer će je upravo podijeliti s vama!

U igri se koriste dvije matrice dimenzija četiri puta četiri (matrica je kvadratna mreža koja se sastoji od određenog broja redaka i stupaca). U obje matrice elementi su nenegativni cijeli brojevi.

Matrica P je matrica prioriteta i ona je fiksna - ne mijenja se tijekom igre. Matrica prioriteta sadrži sve prirodne brojeve između 1 i 16 i to svaki od njih točno jednom.

Matrica M je matrica stanja i ona se mijenja tijekom igre prema pravilima koja ćemo opisati. Na početku igre vrijednost svakog polja matrice M je jednaka 0. Za svako polje matrice M njegov prioritet definiramo kao vrijednost polja na istoj poziciji (u istom retku i stupcu) u matrici P.

Igra se sastoji od niza poteza od kojih svaki donosi određeni broj bodova. Broj bodova na početku igre iznosi 0.

U svakom potezu se mijenja matrica stanja i dobivaju bodovi prema sljedećim pravilima:

• Na početku poteza, od svih polja matrice stanja koje imaju vrijednost 0, ono najvećeg prioriteta se mijenja te postavlja na vrijednost 1. Ako nema niti jedno polje vrijednosti 0, matrica stanja ostaje nepromijenjena.
• Zatim, igrač unošenjem znakova na tipkovnici odabire točno jedan od četiri moguća tipa poteza:
  • Tipkom ‘a’ odabire se potez prema lijevo. Potez se odvija u tri koraka:
    • Poravnanje retka ulijevo: u svakom retku matrice M sve vrijednosti veće od 0 zapisuju se istim redoslijedom počevši od najljevijeg polja u istom retku na desno. Ostala polja u retku poprimaju vrijednost 0. Drugim riječima, redak se preuredi tako da na lijevo dolaze brojevi veći od nule, na desno dolaze nule, a relativni poredak brojeva većih od nule ostane isti. Tako na primjer redak [0 2 0 1] postaje [2 1 0 0].
    • Spajanje susjednih: s lijeva na desno promatramo po dva susjedna polja u retku (najprije prvi i drugi, pa drugi i treći pa treći i četvrti). Ako neka dva polja veća od 0 u trenutku promatranja imaju jednaku vrijednost, vrijednost lijevog polja odmah povećavamo za 1, a vrijednost desnog odmah postaje 0. Ukupan broj bodova povećava se za novu vrijednost lijevog polja.
    • Još jednom se ponovi prvi korak, tj. ponovo se redak poravna ulijevo.
  • Tipkom ‘s’ odabire se analogan potez na stupcima prema dolje.
  • Tipkom ‘d’ odabire se analogan potez na retcima prema desno.
  • Tipkom ‘w’ odabire se analogan potez na stupcima prema gore.

Na primjer, pravilo za tipku ‘s’ dobijemo tako da uzmemo pravila za potez prema lijevo te zamijenimo pojam ‘redak’ sa pojmom ‘stupac’, pojam ‘lijevo’ sa pojmom ‘dolje’, pojam ‘desno’ sa pojmom ‘gore’, pojam ‘najljeviji’ s pojmom ‘najdonji’ itd.

Ilustrirat ćemo pravila tako da prođemo kroz nekoliko poteza. U ovom objašnjenju promatramo samo jedan redak matrice te ilustriramo samo drugi dio poteza kada igrač odabere slovo na tipkovnici.

Napišite program koji će za zadanu matricu prioriteta i niz poteza ispisati trenutno stanje matrice i bodove nakon svakog poteza.

ULAZNI PODACI

U prva četiri retka reda zadana je matrica P i to tako da se u svakom redu nalaze četiri prirodna broja u rasponu od 1 do 16 (uključivo) odvojena razmakom. Dodatno, svaki broj u matrici P je jedinstven.

U sljedećem redu ulaza nalazi se prirodan broj N (1 ≤ N ≤ 1 000), broj poteza.

U svakom od sljedećih N redova ulaza nalazi se jedno od malih slova ‘a’, ‘s’, ‘d’ ili ‘w’ - tipka kojom je odigran potez.

IZLAZNI PODACI

Izlaz se treba sastojati od N blokova gdje i-ti blok sadrži trenutni broj bodova i trenutnu matricu stanja nakon i-tog poteza.

Svaki blok se sastoji od pet redova. Prvi red bloka sadrži jedan cijeli broj - trenutni broj bodova. Zatim slijede četiri reda koja opisuju matricu stanja M u tom trenutku. Svaki red sadrži točno četiri prirodna broja odvojena razmakom - odgovarajući redak matrice M u tom trenutku.

PRIMJERI TEST PODATAKA

ulaz

5 4 15 9
2 12 13 10
3 11 8 14
6 16 1 7
4
a
a
w
d

izlaz

0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
2
0 0 0 0
0 0 0 0
0 0 0 0
2 0 0 0
2
2 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
2
0 0 2 1
0 0 0 0
0 0 0 0
0 0 0 1

ulaz

10 2 3 14
5 16 7 8
9 1 12 11
13 4 15 6
5
s
a
d
w
w

izlaz

0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0
0 0 0 0
1 0 0 0
0 0 0 0
1 0 0 0
2
0 0 0 0
0 0 0 2
0 0 0 0
0 0 0 1
2
0 1 0 2
0 0 0 1
0 0 0 0
0 0 0 0
4
0 2 0 2
0 0 0 1
0 0 0 0
0 0 0 0

ulaz

15 14 4 8
6 7 5 11
16 10 13 3
2 12 9 1
6
d
w
s
d
s
d

izlaz

0
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0
1 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
2
0 0 0 0
0 0 0 0
0 0 0 0
2 0 0 1
2
0 0 0 0
0 0 0 0
0 0 0 1
0 0 2 1
4
0 0 0 0
0 0 0 0
0 0 0 0
1 0 2 2
7
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 3