Državno natjecanje iz informatike 2017. / Srednja škola / Prva podskupina (1. i 2. razred) / prvi dan - 3. zadatak

Rebus je vrsta zagonetke u kojoj se slike i slova kombiniraju kako bi se dobile nove riječi ili fraze. U ovom zadatku se bavimo vrlo jednostavnim rebusima koji se grade samo od riječi te znaka izostavnika kojeg za ovu priliku označavamo pomoću vertikalne crte |.

Riječ je niz od jednog ili više malih slova engleske abecede. Rebus je niz od jedne ili više riječi gdje između svake dvije uzastopne riječi dolazi niz od jednog ili više izostavnika. Dodatno, svaka riječ u rebusu se mora sastojati od barem tri slova. Značenje rebusa je riječ koja se može dobiti na sljedeći način:

• Rebus se umetanjem razmaka podijeli na ispravne stavke: svaka stavka se sastoji od jedne riječi, a neposredno ispred i iza te riječi dolazi niz od nula ili više izostavnika. Stavka je ispravna samo ako je ukupan broj izostavnika u njoj manji od broja slova u njenoj riječi.
• Pronađe se značenje svake pojedine stavke: ako u stavci dolazi točno \(a\) izostavnika ispred riječi i točno \(b\) izostavnika iza riječi onda je značenje stavke riječ koja se dobije brisanjem prvih \(a\) i zadnjih \(b\) znakova iz riječi stavke.
• Spajanjem značenja pojedinih stavki slijeva na desno dobije se značenje rebusa.

Primijetite, da se rebus ponekad može na različite načine rastaviti na ispravne stavke pa da stoga rebus može imati više različitih značenja. Na primjer, rebus lav||||mirko može imati značenja lrko, lako i lavo, dok ne može imati značenje irko jer lav||| |mirko nije rastav rebusa na ispravne stavke.

Zadan je rebus \(r\). Odredite značenje od \(r\) koje dolazi prvo u abecednom (rječničkom) poretku. Možete pretpostaviti da je \(r\) ispravan rebus, odnosno da ima barem jedno značenje.

Ulazni podaci

U prvom redu se nalazi zadani rebus \(r\). Rebus se sastoji od najmanje \(3\) i najviše \(300000\) znakova, a svaki znak je ili malo slovo engleske abecede ili znak | (vertikalna crta, ASCII \(124\)). Niz znakova \(r\) je ispravan rebus prema pravilima iz teksta zadatka. Između ostalog, \(r\) ne može počinjati niti završavati izostavnikom, a svaka pojedina riječ u \(r\) se sastoji od barem tri slova.

Izlazni podaci

U prvi red ispišite jednu riječ — traženo abecedno najmanje moguće značenje.

Bodovanje

• U test podacima vrijednim \(20\%\) bodova između svake dvije riječi u rebusu \(r\) dolazi točno jedan izostavnik.
• U dodatnim test podacima vrijednim \(40\%\) bodova \(r\) se sastoji od najviše \(2000\) znakova.

Primjeri test podataka

Ulaz

mars||||mirko

Izlaz

marko

Ulaz

ana|jede|banane

Izlaz

anaedbanane

Ulaz

baba||baci|||bba

Izlaz

bababa