Državno natjecanje 2012. / Osnovna škola (7. razred) - 3. zadatak Državno natjecanje 2012. / Osnovna škola (8. razred) - 2. zadatak

USS Enterprise-D je naišao na ostatke jedne davno izumrle civilizacije. Posada broda se mjesecima mučila s prevođenjem pronađenih pisanih ostataka. Na kraju su, zahvaljujući kapetanu Picardu i njegovim logičkim igrama s riječima, otkrili da je specifičan način sažimanja (kompresije) teksta odgovoran za probleme s prevođenjem. Pitati Vas da prevedete ovaj jezik bi bilo preteško, pa ste zato dobili suprotan zadatak: da prema hipotezi kako sažimanje radi napišete program za sažimanje zadanog teksta.

Jezik drevne civilizacije koristi \(26\) zamršenih simbola koji su za potrebe zadatka zamijenjeni malim slovima engleske abecede. Tekst je prije sažimanja podijeljen na riječi (nizove znakova) odvojene razmacima, ali sažeti tekst ne sadrži razmake. Sažimanje započinje nepromijenjenim prepisivanjem prve riječi. Sljedeće riječi se dodaju na kraj trenutno sažetog teksta tako da se početak nove riječi (\(0\) ili više znakova, može i cijela nova riječ) preklopi preko istih znakova na kraju kodiranog teksta. Na primjer, dodavanjem riječi ananas na banana možemo dobiti bananaananas (preklapanje \(0\) znakova), bananananas (\(1\)), banananas (\(3\)) ili bananas (\(5\)).

Međutim, riječi se ne dodaju na kraj teksta redoslijedom kojim su zadane! Dodavanje se vrši tako da se odabere ona riječ koja omogućava maksimalno preklapanje (preklapanje najvećeg broja znakova). Ako ima više riječi koje omogućavaju jednaku duljinu preklapanja, bira se najdulja riječ. Ako i dalje odabir nije jednoznačan, uzima se leksikografski najmanja riječ (ona koja bi se u rječniku pojavila prije).

Ako nejednoznačnost još nije riješena, to, naravno, ne utječe na rješenje (dvije identične riječi će se uvijek preklopiti jedna preko druge). Osim što je ovim postupkom promijenjen redoslijed riječi i izgubljene granice među riječima, postoji varijanta sažimanja koja uvodi još jedan postupak. Ta varijanta, osim svih riječi izvornog teksta, u gore opisanom postupku odabira razmatra i obrnute riječi (riječi dobivene čitanjem izvornih riječi s desna na lijevo). Naravno, u završni sažeti tekst će se dodati ili izvorna riječ ili odgovarajuća obrnuta riječ, ali ne obje.

Napišite program koji na temelju izvornog teksta (niza riječi) i podatka koriste li se obrnute riječi izvodi sažimanje i ispisuje sažetu riječ.

Ulaz

• prirodan broj \(N\) \((1 \leq N \leq 100)\), broj riječi koje je potrebno sažeti;
• \(N\) riječi (nizova malih slova engleske abecede) duljine između \(1\) i \(20\) znakova (uključivo), svaka u zasebnom retku ulaza;
• niz znakova DA ili NE (bez navodnika), koji označava koriste li se obrnute riječi;

Izlaz

• prvi red izlaza: prirodan broj – broj znakova u sažetoj poruci;
• drugi red izlaza: niz znakova – poruka sažeta prema tekstu zadatka;

Napomene:

• u test primjerima vrijednima \(50\%\) bodova, zadnji redak ulaza bit će NE (obrnute riječi se neće koristiti);
• programeri u Pascalu trebaju koristiti tip podatka ansistring zbog ograničenosti tipa string;

Primjeri test podataka

Ulaz

2
banana
ananas
NE

Izlaz

7
bananas

Ulaz

8
anna
nannan
aana
aanna
annaa
aannan
aaana
naanan
NE

Izlaz

26
annaanannanaannanaaanaanna

Ulaz

7
we
are
the
borg
resistance
is
futile
DA

Izlaz

27
wecnatsiseraelitufborgehtis