Državna razina / Primjena algoritama OŠ 2025. / Osnovna škola (6. razred) - 3. zadatak

Luka obožava ples i često subotom navečer pleše u lokalnom disko klubu. Plesni podij u tom klubu je malo neobičan - dugačak i uzak, a možemo ga zamisliti i kao niz od N pločica numeriranih brojevima od 1 do N s lijeva na desno. Kada DJ pusti glazbu, Luka se nalazi na početnoj poziciji S. Njegov prepoznatljiv plesni pokret je jednostavan: svake sekunde napravi jedan korak. Započinje krećući se udesno. Kada dođe do desnog kraja podija (pločica N), sljedeći korak radi ulijevo. Kada dođe do lijevog kraja (pločica 1), sljedeći korak radi udesno, i tako se naizmjence kreće po podiju. Preciznije, ako je na pločici i te se kreće desno, u sljedećoj sekundi bit će na pločici i+1. Ako je na pločici N i kreće se desno, promijeni smjer kretanja te u sljedećoj sekundi bude na pločici N-1. Slično vrijedi i za pločicu 1. Međutim, neke pločice na podiju imaju specijalne efekte. Ako Luka stane na nju, tada:

• 'A' pločica: umjesto normalnog koraka, trenutačno se teleportira A pločica u smjeru u kojem se trenutno kreće;

• 'B' pločica: umjesto normalnog koraka, trenutačno se teleportira B pločica u smjeru suprotnom od onog u kojem se trenutno kreće;

• 'C' pločica: ostaje na toj pločici, ali se efekt 'A' i 'B' pločica trajno zamijeni za sve buduće korake! Od tog trenutka, 'A' pločice uzrokuju teleportaciju B pločica u suprotnom smjeru, a 'B' pločice uzrokuju teleportaciju A pločica u trenutnom smjeru. Ako Luka ponovno stane na 'C' pločicu, efekti se opet vrate na originalne. Svako stajanje na 'C' mijenja trenutno aktivne efekte A i B pločica.

Važna pravila teleportacije: Teleportacija se događa nakon normalnog koraka u toj sekundi i traje nula sekundi. Ako teleportacija odvede Luku na normalnu pločicu, on sljedeće sekunde nastavlja normalnim korakom. Ako teleportacija Luku odvede na 'A' ili 'B' pločicu, tada Luka opet biva teleportiran i to se ponavlja tako dugo dok ne završi na normalnoj pločici ili 'C' pločici. Teleportacija ne mijenja smjer kretanja. Primjeti da je moguće da Luka nikad neće stati, tj. zauvijek će se teleportirati po plesnom podiju. Ako bi teleportacija trebala Luku teleportirati izvan plesnog podija, tada Luka u toj sekundi izađe iz diska i ode kući spavati. Ako znamo da DJ pušta glazbu točno K sekundi, odredi je li Luka otišao doma spavati, je li možda zapeo u vječnoj teleportaciji ili, ako je otplesao cijeli ples, na kojoj će se pločici nalaziti nakon K sekundi plesa?

Ulazni podaci

U prvom su retku prirodni brojevi N, S, K, A i B (2 ≤ N ≤ 30, 1 ≤ K, A, B ≤ 100, 1≤ S ≤ N-1 ), duljina plesnog podija, početna pozicija Luke, broj sekundi koliko DJ pušta glazbu, broj pločica koliko 'A' pločica teleportira Luku i broj pločica koliko 'B' pločica teleportira Luku.

U idućem retku nalazi se riječ duljine N znakova u kojoj i-ti znak opisuje kakva je i-ta pločica: '.' označava normalnu pločicu, dok su 'A', 'B' i 'C' pločice označene tim slovima. Prva i zadnja pločica bit će normalne.

Luka će se na početku nalaziti na normalnoj pločici.

Izlazni podaci

Ako je Luka otišao doma spavati ispiši u prvom retku riječ SPAVANJE, a u drugom retku sekundu u kojoj se to dogodilo.

Ako je Luka zapeo u teleportaciji, tj. zauvijek će se teleportirati po plesnom podiju ispiši u prvom retku riječ TELEPORTACIJA, a u drugom sekundu u kojoj se dogodila prva od beskonačnog broja teleportacija.

Ako je Luka otplesao cijeli ples, u prvi redak ispiši riječ FAJRUNT, a u drugi redak na kojoj pločici se Luka nalazio nakon K sekundi.

Bodovanje

U primjerima vrijednima 30 bodova Luka će otići doma.

U primjerima vrijednima 30 bodova Luka će zapeti u teleportaciji.

U primjerima vrijednima 30 bodova Luka će otplesati cijeli ples.

Primjer zadatka

Ulaz

5 3 14 3 1 
.B..C

Izlaz

SPAVANJE
5

Ulaz

10 1 9 2 3
.A.C.B.C..

Izlaz

FAJRUNT
4

Ulaz

6 1 8 2 2
.CAAB.

Izlaz

TELEPORTACIJA
4

Opis prvog probnog primjera:

1. sekunda - Luka je na 3. pločici; 1. sekunda - Luka je na 4. pločici; 2. sekunda - Luka je na 5. pločici
2. sekunda - Luka je na 4. pločici; 4. sekunda - Luka je na 3. pločici
3. sekunda - Luka staje na 2. pločicu koja je B pločica, a kako je u 2. sekundi stao na C pločicu, trenutna pločica ga teleportira tri pločice u smjeru kretanja i tako on završi izvan podija te ode kući spavati.

Opis trećeg probnog primjera:

1. sekunda - Luka je na 1. pločici; 1. sekunda - Luka je na 2. pločici (C pločica mijenja svojstva A i B); 2. sekunda - Luka staje na 3. pločicu koja ga teleportira 2 pločice suprotno smjeru kretanja i tako Luka završava na 1. pločici.
2. sekunda - Luka je na 2. pločici; 4. sekunda - Luka staje na 3. pločicu koja ga teleportira 2 pločice u smjeru kretanja (desno). Nakon teleportacije on je na 5. pločici koja je B pločica i ona ga teleportira 2 pločice u smjeru suprotnom smjeru kretanja (lijevo). Nakon toga opet se nalazi na 3. pločici koja ga teleportira opet 2 pločice desno itd. Kratko rečeno, Luka je zapeo u vječnoj teleportaciji.