Prioritetne Liste Želja

Djed Božićnjak svake godine prima gomilu nepreglednih pisama s prioritetnim (!) listama želja. Svaka lista ima točno 100 želja. Kako bi pomogli Djedovim pomoćnicima u organizaciji, želje se pojednostavljuju kategorizacijom u slova:

I: igračke
B: bomboni
E: elektronika
S: sportska oprema
K: knjige
D: društvene igre
P: puzzle
O: odjeća
G: glazbeni instrumenti
L: lego

Primjer pojednostavljenje liste:

EBDBDIDKKOOSSSDOLSIGIKSOKOKKPLKGBGBEDPDKKDIIPDSEPSSLGPDOKGIPGPDDOOEDLDPGDGDOOEESIPEPGGBDKEEGIISOISDL

Time nastaju stringovi koji predstavljaju prioritetne liste želja (redoslijed slova je bitan). Kako su liste prioritetne, pomoćnici ne smiju mijenjati redoslijed slova. Međutim, veliki broj tih lista usporava proizvodnju, pa Djed traži tvoju pomoć da pronađe "srednju listu". Ta lista definira se kao ona lista koja ima najmanju Hammingovu udaljenost od svake početne liste.

Hammingova udaljenost definira se kao broj indeksa na kojima dva stringa imaju različite elemente.

Srednja lista određuje se s dva kriterija (prvi nosi 70% bodova, a drugi 30%):

Najmanja Hammingova udaljenost, vaš cilj je minimizirati maksimalnu Hammingovu udaljenost između vašeg izlaznog stringa i svih ulaznih stringova
Zbroj Hammingovih udaljenosti, vaš cilj je minimizirati zbroj svih Hammingovih udaljenosti izlaznog stringa i svih ulaznih stringova

Na primjer, ako Hammingove udaljenosti izlaznog niza i ulaznih nizova iznose 2, 3, 1, 4, 2 onda:

Maksimalna udaljenost = 4

Zbroj udaljenosti = 2 + 3 + 1 + 4 + 2 = 12

Primjer

Ulaz

Radi jednostavnosti recimo da su ulazni stringovi duljine 5 (u pravim ulaznim podatcima svi su duljine 100):

IBESI
ISBEI
IBSSI
EBSIS
ISSEB

Izlaz

Vaš program bi mogao vratiti izlazni niz:

IBSEI

Za ovaj izlazni niz, računate:

Najveća Hammingova udaljenost: Hammingove udaljenosti vašeg stringa i ulaznog stringa su 2, 2, 1, 3, 2. Znači za ovaj kriterij biste dobili (5 - 3) / 5 bodova. 5 je duljina svih stringova, a 3 je maksimalna Hammingova udaljenost

Suma Hammingovih udaljenosti: Hammingove udaljenosti vašeg stringa i ulaznog stringa su 2, 2, 1, 3, 2. Znači suma je 10, vaš broj bodova za ovaj kriterij bio bi (5 _ 5 - 10) / (5 _ 5). 5 je broj ulaznih stringova i duljina ulaznih stringova, a 10 je suma Hammingovih udaljenosti

Bodovanje

Vaš ukupan broj bodova bit će zbroj ovih dvaju kriterija:

70% bodova: Najmanja maksimalna Hammingova udaljenost, broj bodova računa se prema formuli (100 - max(Hammingova_udaljenost(s, si))) / 100, gdje je s vaš izlazni string, si je svaki ulazni string, a 100 je duljina ulaznih stringova

30% bodova: Minimalna suma Hammingovih udaljenosti, broj bodova računa se kao (1000 _ 100 - suma) / (1000 _ 100) gdje je 1000 broj ulaznih stringova, 100 je duljina svakog stringa, a suma je suma svih Hammingovih udaljenosti.

Ulazni podaci

1000 redaka, gdje svaki redak sadrži niz od 100 slova (I, B, E, S, K, D, O, P, G, L) koji predstavlja prioritetnu listu želja.

Izlazni podaci

Izlazni niz od 100 slova koji zadovoljava navedene kriterije i ostvaruje maksimalan broj bodova.

Zadaci