Srednješolsko tekmovanje ACM iz računalništva in informatike

Stiskanje nizov

Podroben opis naloge

Dan je niz znakov s, ki ga sestavljajo same male črke angleške abecede. Tak niz lahko včasih opišemo kot stik več krajših nizov, pri čemer se nekateri krajši nizi lahko pojavljajo po večkrat. Pri tej nalogi bomo ocenili takšno razbitje niza na podnize tako, da bomo sešteli dolžine vseh različnih nizov v razbitju in tej vsoti prišteli število vseh nizov v razbitju.

Tvoja naloga je torej, da za dani niz s poiščeš nek nabor nizov t₁, t₂, . . . , t_k in zaporedje indeksov i₁, i₂, . . . , i_r, tako da bo veljalo s = t_i₁ t_i₂ . . . t_{i_r}. Pri tem moraš minimizirati oceno r + |t₁| + |t₂| + . . . + |t_k|, torej vsoto dolžine zaporedja indeksov i_• ter skupne dolžine vseh nizov t_•. (Tukaj nam zapis |x| pomeni dolžino niza x.)

Primer: recimo, da imamo s = ananas. Nekaj možnih rešitev je potem:

k = 2, t₁ = nos, t₂ = ananas, r = 1, i₁ = 2. Ocena te rešitve je k + |t₁| + |t₂| = 1 + 3 + 6 = 10. Ta rešitev je zelo slaba, saj med t-ji vsebuje en niz, ki ga pri tvorbi niza s sploh ne potrebuje.
k = 2, t₁ = an, t₂ = as, r = 3, i₁ = 1, i₂ = 1, i₃ = 2. Ocena te rešitve je 3 + 2 + 2 = 7. Niz ananas smo torej sestavili kot an + an + as.
k = 3, t₁ = s, t₂ = na, t₃ = a, r = 4, i₁ = 3, i₂ = 2, i₃ = 2, i₄ = 1. Ocena te rešitve je 4 + 1 + 2 + 1 = 8. Niz ananas smo torej sestavili kot a + na + na + s.

Možne so seveda tudi še drugačne rešitve. Med zgornjimi tremi je najboljša druga od njih (z oceno 7).

Ocenjevalni program

Lahko si preneseš izvorno kodo programa, s katerim bomo ocenjevali prejete rešitve: Rtk20Stiskanje.cpp.

Na voljo je tudi prevedena različica ocenjevalnega programa (za Windows).

Oblika vhodne datoteke

Pri tej nalogi so vsi testni primeri podani v eni vhodni datoteki. V prvi vrstici vhodne datoteke je niz z imenom naloge (Stiskanje), v drugi pa število testnih primerov (T). Sledijo testni primeri, pred vsakim od njih pa je še ena prazna vrstica.

Vsak testni primer se začne z vrstico, ki vsebuje številko tega testnega primera (od 1 do T), sledi pa ji vrstica, ki vsebuje niz s za ta testni primer. Ta niz sestavljajo same male črke angleške abecede.

Primer: če bi imeli en sam testni primer, in sicer niz ananas (ki smo ga videli že v primerih zgoraj), bi bila vhodna datoteka takšna:

Stiskanje
1

1
ananas

V resnici bo pri tej nalogi 10 testnih primerov.

Oblika izhodne datoteke

Oddaš lahko poljubno število izhodnih datotek s svojimi rešitvami. Pri tem vsaka izhodna datoteka vsebuje rešitve za enega ali več testnih primerov. Če za isti testni primer oddaš več rešitev, bomo pri ocenjevanju upoštevali najboljšo med njimi.

Oblika posamezne izhodne datoteke je naslednja:

V prvi vrstici naj bo koda, ki si jo dobil(a) ob registraciji in iz katere je razvidno, da si rešitev res poslal(a) ti, ne pa kdo drug. V drugi vrstici naj bo ime naloge (Stiskanje). Sledijo naj tvoje rešitve za enega ali več testnih primerov.

Vsaka rešitev se začne s prazno vrstico. Sledi naj vrstica, ki vsebuje številko testnega primera (od 1 do T), na katerega se ta rešitev nanaša. Sledi naj vrstica, ki vsebuje števili k in r, ločeni z enim presledkom. Sledi naj k vrstic, ki naj po vrsti vsebujejo nize t₁, . . . , t_k. Sledi naj še ena vrstica, ki vsebuje števila i₁, . . . , i_r, ločena s po enim presledkom.

Posamezni niz t_j mora biti sestavljen iz samih malih črk angleške abecede, dolg mora biti vsaj 1 znak in ne sme biti daljši od niza s. Tudi k in r ne smeta biti večja od dolžine niza s.

Primer: če bi bila naša uporabniška koda enaka 123456 in bi obstajal prvi testni primer, kakršen je prikazan zgoraj, bi lahko oddali spodnjo izhodno datoteko.

123456
Stiskanje

1
2 3
an
as
1 1 2

Ta rešitev je veljavna (ananas = an + an + as) in ima oceno 3 + 2 + 2 = 7.

Vhodni podatki

stiskanje.in — datoteka z vsemi vhodnimi podatki za to nalogo.
stiskanje-unix.in — ista datoteka, vendar z unixaškimi konci vrstic (LF namesto CRLF).

Registracija

Preden lahko oddajaš svoje rešitve, se prijavi prek spodnjega obrazca. Dodelili ti bomo enolično uporabniško kodo, ki jo boš potreboval(a) za pripravo svojih izhodnih datotek.

Opomba: pri tej nalogi lahko sodeluje kdorkoli, ne glede na starost, izobrazbo, itd. Objavili bomo rezultate vseh tekmovalcev, za morebitne praktične nagrade pa pridejo v poštev le srednješolci/ke in študentje/ke.