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

Svaki mudar čovjek reći će da se u životu treba baviti nekim sportom, barem rekreativno.

Onaj još mudriji reći će da to treba biti badminton.

Badminton se igra na pravokutnom terenu kojeg na dva dijela dijeli mreža.

Svaki je igrač s jedne strane mreže, u svojoj polovici terena.

Kada je igrač okrenut prema mreži, njegovu polovicu možemo podijeliti na lijevo servisno polje i desno servisno polje.

Servis je udarac kojim igrači započinju poen.

Igrač servira dijagonalno, iz svog lijevog ili desnog servisnog polja.

Na kraju poena, jedan od igrača osvaja taj poen i za to dobiva jedan bod.

Servis izvodi igrač koji je osvojio prethodni poen.

Igrač servira iz svog lijevog servisnog polja ako je taj igrač do tog trenutka osvojio neparan broj bodova, a inače servira iz svog desnog servisnog polja.

Mirko je za jednu svoju igru, u kojoj je on servirao prvi, zapisao iz kojih su se servisnih polja redom izvodili servisi (lijevo ili desno iz perspektive igrača koji servira), no nije zapisao tko je izvodio servis.

Mirko je primjetio da s ovim podatcima krajnji rezultat nije jednoznačno određen.

Pomozite Mirku i izračunajte koliko je najviše poena on mogao osvojiti u toj igri na temelju zadanih podataka.

Moguće je da su podatci nekonzistentni, tj. da ne postoji valjani tijek igre koji im odgovara.

Moguće je i da je za neke servise Mirko zaboravio upisati lijevu ili desnu stranu, a u tom slučaju na odgovarajućem mjestu stoji upitnik.

ULAZNI PODACI

U prvom je retku prirodan broj N (1 ≤ N ≤ 100), ukupan broj odigranih poena u igri.

U drugom je retku niz od N znakova ‘L’ ili ‘D’, oznake lijeve ili desne strane s koje je igrač koji servira izvodio servis. Ako strana nije zapisana, na odgovarajućem mjestu stajat će znak ‘?‘, a takvih će znakova biti najviše 15.

IZLAZNI PODACI

U jedinom retku ispišite koliko je najviše poena Mirko mogao osvojiti, ili broj -1 ako podatci ne odgovaraju valjanoj igri.

Primjeri test podataka

Ulaz

4
DLLD

Izlaz

3

Objašnjenje

Pojašnjenje prvog primjera: U jednom mogućem scenariju, Mirko najprije servira s desne strane (jer na početku ima 0 bodova, što je paran broj) i osvaja poen.

Potom servira s lijeve strane i gubi poen. Stoga u idućem poenu servira njegov protivnik (s lijeve strane jer ima 1 bod), ali gubi poen.

U zadnjem poenu servira Mirko s desne strane (jer ima 2 boda) i osvaja treći poen.

Ulaz

6
DLDDDL

Izlaz

-1

Ulaz

6
D?L?D?

Izlaz

4

Objašnjenje

Pojašnjenje trećeg primjera: U jednom mogućem scenariju, poene osvajaju redom Mirko, protivnik, Mirko, protivnik, Mirko, Mirko, a niz servisnih polja jest DLLDDL.