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

Mirko je odlučio šifrirati tekst tako da je svako slovo zamijenio određenom riječju. Tako je dobio besmislen niz riječi.

Slavko je odlučio “probiti” Mirkovu šifru promatrajući učestalosti pojavljivanja pojedinih riječi.

Na primjer, riječi koje se često pojavljuju vjerojatno potječu od samoglasnika.

Takav pristup zove se frekvencijska analiza.

Tvoj je zadatak pomoći Slavku i napraviti prvi korak frekvencijske analize.

Preciznije, napiši program koji Mirkov niz riječi sortira (mijenja mu redoslijed) prema sljedećim kriterijima:

1. Riječi valja poredati silazno po učestalosti. Dakle, niz treba započeti riječima koje se u Mirkovom tekstu pojavljuju najčešće (najviše puta), a završiti riječima koje se pojavljuju najrjeđe (najmanje puta).
2. Ako su neke riječi jednako česte, gleda se njihova duljina, tj. prije treba doći ona riječ koja je dulja.
3. Ako su neke riječi jednako česte, a i jednake duljine, prednost ima ona koja se u Mirkovom nizu prije pojavljuje.

Dio test podataka sadrži slučajeve koje je moguće riješiti i nekim nepotpunim rješenjima, tj. rješenjima koja primjenjuju samo neke od navedenih kriterija (vidi sekciju Bodovanje).

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (3 ≤ N ≤ 20), broj riječi u nizu.

Sljedećih N redaka sadrže zadani niz riječi. U svakom retku nalazi se riječ sastavljena od 1-20 malih slova engleske abecede.

IZLAZNI PODATCI

Ispiši N redaka u kojima se nalazi niz riječi sortiran po navedenim pravilima.

PRIMJERI TEST PODATAKA

Ulaz

6
skola
je
skola
ali
je
skola

Izlaz

skola
skola
skola
je
je
ali

Ulaz

4
petar
petru
petlju
plete

Izlaz

petlju
petar
petru
plete

Ulaz

6
ili
ces
uciti
ili
ces
kopati

Izlaz

ili
ili
ces
ces
kopati
uciti