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 t1, t2, . . . , tk in zaporedje indeksov i1, i2, . . . , ir, tako da bo veljalo s = ti1 ti2 . . . tir. Pri tem moraš minimizirati oceno r + |t1| + |t2| + . . .  + |tk|, 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:

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 t1, . . . , tk. Sledi naj še ena vrstica, ki vsebuje števila i1, . . . , ir, ločena s po enim presledkom.

Posamezni niz tj 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

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.

Ime in priimek: *
e-mail: *
Šola:
Letnik:
Mentor:
 

Obrazec za oddajo rešitev

(Oddaja rešitev je možna do vključno 27. marca 2020.)

Datoteka s tvojo rešitvijo:

[Nazaj na glavno stran. | Na vrh te strani. | Imate vprašanje ali komentar?]