Županijsko natjecanje 2017. / Osnovna škola (8. razred) - 2. zadatak

Robot se kreće po točkama pravokutnog koordinatnog sustava u ravnini.

Zadana je njegova putanja kao string sastavljen od znakova S (“idi sjeverno tj. gore”), J (“idi južno tj. dolje”), I (“idi istočno tj. desno”) te Z (“idi zapadno tj. lijevo”).

Robot očitava string i svake sekunde se miče u odgovarajućem smjeru.

Na primjer, ako se robot nalazi u ishodištu, tj. u točki (0, 0), nakon naredbe Z putuje u točku (-1, 0) tijekom jedne sekunde.

U ovom zadatku dva su robota, označeni s A i B, i svakome je zadana njegova putanja.

Robot A kreće iz ishodišta.

Robot B također kreće iz ishodišta, ali 5 sekundi kasnije, nakon što je robot A već učinio 5 koraka.

Dakle, robot A čini svoj 6. korak istodobno s 1. korakom robota B.

Ovisno o duljinama njihovih putanja, moguće je da se jedan od robota kreće i nakon što drugi završi s kretanjem.

Ako se roboti susretnu na pola nekog koraka, prolazeći istom dužinom u suprotnim smjerovima, kažemo da se dogodio sudar. (Sudar neće omesti kretanje robota.)

Napiši program koji učitava putanju ovih robota te ispisuje:

1. broj sudara,
2. broj različitih cjelobrojnih točaka koje je posjetio robot A,
3. broj različitih cjelobrojnih točaka koje je posjetio robot B,
4. broj različitih cjelobrojnih točaka koje su barem jednom posjećene.

ULAZNI PODATCI

U prvom retku nalazi se putanja robota A, string od 6-20 znakova opisanih u tekstu zadatka.

U drugom retku nalazi se putanja robota B, string od 1-20 znakova opisanih u tekstu zadatka.

IZLAZNI PODATCI

Ispišite tražene brojeve zadanim redoslijedom, svaki u svoj redak.

PRIMJERI TEST PODATAKA

Ulaz

SIIJZZ
IZ

Izlaz

1
6
2
6

Objašnjenje

Pojašnjenje prvog test podatka:

Tijekom prvih 5 sekundi robot A kreće se ovako: (0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 0) → (1, 0).

U 6. sekundi putuje prema (0, 0) i sudara se robotom B koji čini svoj prvi korak prema (1, 0).

U 7. sekundi kreće se samo robot B, natrag u točku (0, 0). Dogodio se ukupno jedan sudar.

Ulaz

JZJZJZ
Z

Izlaz

0
7
2
8

Objašnjenje

Pojašnjenje drugog test podatka:

Roboti završavaju kretanje u isto vrijeme. Nema sudara.

Posjećeno je 8 različitih točaka: (0, 0) od obaju robota, (-1, 0) od robota B, te (0, -1), (-1, -1), (-1, -2), (-2, -2), (-2, -3) i (-3, -3) od robota A.