Državno natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 1. zadatak

Toranj u društvenoj igri Jenga sastoji se od katova od kojih je svaki na početku igre sačinjen od tri Jenga-pločice jednake veličine, dvije na rubu kata i jedna između njih. Igrači tijekom igre izvlače pločice iz tornja i stavljaju ih na vrh tornja gradeći nove katove i pazeći da se toranj ne uruši.

Da se dio tornja iznad pojedinog kata ne bi srušio, kat mora biti dovoljno stabilan, tj. mora sadržavati barem srednju pločicu ili barem obje rubne pločice. Drugim riječima, kat se ruši kada ostane bez srednje i jedne rubne pločice. U ovom zadatku riječ je o Jenga Gold inačici igre u kojoj je svaka pločica ili zlatna ili pozlaćena. Zlatnu pločicu označavamo slovom Z, pozlaćenu slovom P, a prazno mjesto točkom, pa tako kat može biti opisan npr. kao „ZP.“ (rubna pločica je zlatna, srednja pozlaćena, a druga rubna nedostaje) ili kao „.Z.“ (preostala je samo srednja zlatna pločica).

U pojedinom potezu igrač vadi bilo koju pločicu iz nekog kata koji nije najviši. (Moguće je izvaditi i srednju pločicu ako su obje rubne pločice prisutne.) Ako izvuče pločicu bez rušenja, igrač pogleda je li izvučena pločica zlatna ili pozlaćena. Ako je zlatna, igrač zadržava pločicu i ne vraća je na toranj. Ako je pločica pozlaćena, igrač je mora staviti na najviši kat tornja (na bilo koje slobodno mjesto) ako taj kat sadrži manje od tri pločice. Ako najviši kat već sadrži tri pločice, igrač izvučenom pozlaćenom pločicom započinje gradnju novog najvišeg kata stavljajući je na vrh kao prvu rubnu ili srednju pločicu. Primijetite da je moguće da pločica tijekom igre bude više puta izvučena iz tornja.

Napišite program koji učitava strukturu tornja u nekom trenutku igre te računa najveći mogući broj poteza koji bi se još mogli odigrati bez rušenja tornja (u najboljem slučaju).

Ulazni​ podaci

U prvom retku nalazi se prirodan broj \(N ( 2 \leq N \leq 20 )\), trenutačni broj katova tornja. Svaki od sljedećih \(N\) redaka opisuje jedan kat tornja kao niz triju znakova opisan u tekstu zadatka. Katovi su zadani od najvišeg do najnižeg. Svaki kat bit će stabilan (prema uvjetu iz teksta zadatka) osim možda najvišeg kata, ali i on će sadržavati barem jednu pločicu.

Izlazni podaci

U jedini redak ispišite traženi maksimalan broj poteza.

Bodovanje

U test podatcima ukupno vrijednim \(30 \%\) bodova sve pločice bit će zlatne. U test podatcima ukupno vrijednim \(30 \%\) bodova sve pločice bit će pozlaćene.

Primjeri test​ podataka

Ulaz

4
..Z
P.P
PP.
ZPZ

Izlaz

3

Ulaz

4
ZZP
.ZP
PZ.
ZPZ

Izlaz

7