Županijsko natjecanje 2015 / Osnovna škola (8. razred) - 3. zadatak

Zamislimo neko raskrižje dviju ulica na kojem nema semafora koji bi regulirali prolazak vozila kroz njega.

Pretpostavimo da je AC glavna, a BD sporedna ulica na ovom raskrižju.

Postoji nekoliko pravila kojima određujemo redoslijed ulaska vozila u raskrižje:

• istovremeno se promatraju samo vozila koja su tik pred raskrižjem;
• kažemo da vozilu X smeta vozilo Y ako vrijede obje sljedeće tvrdnje:
  • putanje prolaska kroz raskrižje im se presijecaju ili spajaju;
  • Y ima prednost nad X;
• istodobno prolaze ona vozila kojima nijedno vozilo ne smeta.

Presijecanje putanja vidljivo je sa slike.

A što je prednost?

Ako su X i Y dva vozila, prednost ima ono vozilo koje dolazi s glavne ceste.

Ako su po tom kriteriju vozila jednaka (oba su na glavnoj ili oba na sporednoj cesti), prednost ima vozilo koje ne skreće lijevo.

Ako su i po tom kriteriju vozila jednaka, nijedno od njih nema prednost pred drugim.

Nakon što neko vozilo uđe u raskrižje, na njegovo mjesto pred raskrižjem odmah dolazi novo vozilo (ako ih ima) i pravila se primjenjuju ponovno.

Moguće je da neko vozilo uzastopno čeka više puta na prolazak.

Napiši program koji će ispisati oznaku one ulice iz koje je prvi auto ušao u raskrižje.

Ako su u tom prvom prolazu auti iz više ulica ušli u raskrižje, tada treba ispisati oznake ulica iz kojih dolaze abecednim redom.

Dodatno, ako znamo da za jedan prolazak kroz raskrižje (bez obzira koliko auta istovremeno prolazi kroz njega) treba jedna sekunda, ispiši koliko sekundi treba da sva vozila prođu raskrižjem.

Ulazni podaci

U prvom retku nalazi se string sastavljen samo od znakova “L”, “D” i “R”.

Znak na i-tom mjestu u stringu definira smjer kretanja i-tog vozila u redu vozila koja stoje u ulici s oznakom A (prvi znak je smjer kretanja prvog vozila u redu, itd).

Pri tome vrijedi da je “L” oznaka za lijevo skretanje, “D” za desno i “R” za zadržavanje smjera.

Broj vozila u svakoj od ulica neće biti veći od 15.

Isti oblik podataka nalazi se u drugom, trećem i četvrtom retku te predstavlja stanje u ulicama B, C i D tim redom. Znak “*” umjesto opisanog stringa označava praznu ulicu na početku promatranja.

Na početku, barem jedna ulica neće biti prazna.

Izlazni podaci

U prvi redak treba ispisati jedno ili više velikih slova A, B, C i D bez razmaka, tražene oznake ulica iz teksta zadatka.

U drugi redak treba ispisati prirodan broj, traženi broj sekundi iz teksta zadatka.

Primjeri test podataka

Ulaz

L
R
R
*

Izlaz

C
3

Objašnjenje

Pogledaj sliku. Vidljivo je da je raskrižjem prvo prošao auto iz ulice C, pa auto iz ulice A i na kraju auto iz ulice B.

Ulaz

R
L
R
D

Izlaz

AC
3

Objašnjenje

Auti su kroz raskrižje prošli u tri sekunde. Pri tome vrijedi da su u prvoj sekundi prošli auti iz AC, pa auto iz D i na kraju auto iz B.

Ulaz

LRRLRD
DRRD
DLLRD
LDD

Izlaz

BC
13

Objašnjenje

U 13 sekundi dogodili su se sljedeći prolazi: BC-AC-A-A-AC-AC-AC-B-B-BD-D-D