Županijsko natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 4. zadatak

Nekoliko znanstvenika koji se bave genetikom na jednom poznatom svjetskom institutu imaju problema s količinom podataka koje trebaju pohraniti. Naime, radi istraživanja u svoj sustav pohranjuju genetske kodove (nizove dušikovih baza) velikog broja ljudi. Svaki kod se sastoji isključivo od A, C, T i G slova.

Želedi izvršiti kompresiju kodova koje proučavaju, odlučili su određene krade kodove dušikovih baza zamijeniti kraticama. Takve kodove nazivaju specijalnim kodovima. Pokušali su ručno zamjenjivati dijelove DNA koda kraticama, ali su shvatili da je to poprilično komplicirano. Zato su vas zamolili da im napišete program koji de izvršiti optimalnu kompresiju DNA koda koristedi njihove specijalne kodove i pripadajude im kratice.

Znanstvenici de vam dati niz dušikovih baza jedne osobe, a potom i listu manjih specijalnih kodova za koje su dogovorili dužine zamjenskih kratica. Zanima ih s koliko se najmanje slova može zapisati zadani DNA kod, ako se kod optimalno komprimira koristedi njihove kratice.

ULAZNI PODACI

U prvom retku se nalazi DNA kod koji treba komprimirati, dužine N ( 1 ≤ N ≤ 1 000 000 ).

U drugom redu se nalazi broj M ( 1 ≤ M ≤ 20 ), koji predstavlja broj kratica.

U slijededih M redaka se nalazi DNA niz i razmakom odvojen jedan broj koji predstavljaju i-ti DNA niz, maksimalne dužine K ( 1 ≤ K ≤ 1000 ) i dužinu kratice kojom se može zamijeniti L ( 1 ≤ L ≤ 1000 ).

IZLAZNI PODACI

U prvom i jedinom retku potrebno je ispisati dužinu optimalno komprimiranog DNA koda.

PRIMJERI TEST PODATAKA

ulaz

ATTCGAT
2
ATT 1
CGAT 2

izlaz

3

ulaz

TATACATAT
2
TACA 1
AT 1

izlaz

5

ulaz

GAGATAGACTAC
3
GA 1
AGA 2
AGAC 3

izlaz

9

Objašnjenje

Objašnjenje trećeg test primjera: Optimalnu kompresiju dobijemo ako na ovaj način zamijenimo specijalne kodove (GA)(GA)T(AGAC)TAC. Umjesto dva slova „GA“ biti će kratica dužine jednog slova, umjesto „AGAC“ biti će kratica dužine 3 slova pa tako ukupna dužina ovog komprimiranog DNA niza je 9 slova ( 1 + 1 + T + 3 + TAC).