Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 250M

Problem type

Bio jednom jedan film. Vi stojite ispred bioskopa i pitali ste N ljudi da vam ispričaju jednu scenu iz filma. Kako su pukom koincidencijom svi ti ljudi takođe odlični programeri kao i vi, svako od njih vam je ispričao jednu scenu, predstavljenu kao string malih slova engleske abecede, uz napomenu da se ta scena javlja u filmu tačno jednom. Vaš zadatak je da rekonstruišete film, tačnije, da pronađete string S najkraće moguće dužine koji će svaku scenu sadržati tačno jednom, takav da se taj string sastoji samo od prvih K malih slova engleske abecede.

Opisi funkcija

Potrebno je da implementirate funkciju

  • Resi(N, K, L[\ldots], A[\ldots][\ldots], S[\ldots])

koja treba da nađe string opisan u tekstu zadatka. N označava broj ljudi koji su vam rekli jednu scenu iz filma. K je broj koji označava koliko prvih malih slova engleske abecede možete koristiti za konstruisanje filma. L je niz dužine N koji sadrži dužine datih scena. A je niz nizova, gde elementi A[i][1], \ldots, A[i][L[i]] čine i-tu scenu. Svi ovi elementi su mala slova engleske abecede. Ukoliko takav string postoji, pronađeni string minimalne dužine smestite u niz S počev od pozicije 1, a njegovu dužinu vratite kao rezultat funkcije. Ukoliko takav string ne postoji, dovoljno je da iz funkcije vratite broj -1. Garantuje se da će za string S biti rezervisano dovoljno memorije da ceo rezultujući string može da stane. Svi nizovi su indeksirani od 1.

Primeri

Primer 1

Neka je N=6, K=26, a stringovi su ave, venge, ger, rs, r, av. Rešenje je string avengers. Vaša funkcija treba da upiše ovaj string na pozicije S[1], \ldots, S[8] i da vrati broj 8.

Primer 2

Neka je N=2, K=2, a stringovi su ababa, aba. Rešenje ne postoji. U ovom slučaju dovoljno je da vaša funkcija vrati broj -1.

Ograničenja

  • 1 \leq N \leq 14
  • 1 \leq K \leq 26
  • L_i \geq 1
  • \sum_{i=1}^N L_i \leq 150

Podzadaci

  • Podzadatak 1 [14 poena]: K = 2, ukoliko rešenje postoji, tada je ono ne duže od 18.
  • Podzadatak 2 [12 poena]: N = 2
  • Podzadatak 3 [23 poena]: N = 3
  • Podzadatak 4 [51 poen]: Bez dodatnih ograničenja.

Detalji implementacije

Potrebno je da pošaljete tačno jedan fajl film.cpp, koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.

Vaša funkcija mora biti sledećeg oblika:

int Resi(int N, int K, int* L, char** A, char* S);

Vašim programima je dozvoljeno da menjaju sadržaj nizova/matrica, ali ne smeju da pristupaju van granica datih nizova.

Testiranje i eksperimentisanje

Uz zadatak, obezbeđen vam je "template" fajl code.cpp koji možete koristiti i menjati po potrebi. Takođe vam je obezbeđen program grader.cpp koji služi da lakše testirate kodove. Ovaj program učitava sa standardnog ulaza sledeće podatke:

  • U prvom redu brojeve N, K,
  • U narednih N redova po jedan string - A_i.

Zatim ovaj program zove vašu funkciju. Neka je vaša funkcija vratila broj X. Ukoliko je X < 0, štampa se samo X. U suprotnom, štampa se X i prvih X karaktera niza S. Kodove ovih programa možete menjati po potrebi.


Comments

There are no comments at the moment.