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

Stiskanje nizov

To je „off-line naloga“. Na tej spletni strani je objavljen opis naloge in testni primeri. Svoje rešitve lahko pošlješ prek obrazca na tej strani kadarkoli do vključno 27. marca 2020 (dan pred tekmovanjem).

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. Na primer: zaplapolalo lahko zapišemo kot zap + la + po + la + lo (niz la se pojavlja dvakrat) ali pa kot z + ap + l + ap + olalo (niz ap se pojavlja dvakrat) ali še na razne druge načine.

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. Za drugega izmed zgornjih primerov, zaplapolalo = z + ap + l + ap + olalo, imamo na primer v razbitju pet nizov (z, ap, l, še en ap in na koncu še olalo), različni pa so štirje (z, ap, l, olalo) s skupno dolžino 1 + 2 + 1 + 5 = 9. Ocena tega razbitja je torej 9 + 5 = 14.

Tvoja naloga je za dan vhodni niz poiskati čim boljše razbitje na podnize (torej tako, pri katerem je ocena po definiciji iz prejšnjega odstavka čim nižja).

Še en primer: recimo, da imamo s = kanetkananet. Nekaj možnih rešitev je potem:

Možne so seveda tudi še drugačne rešitve. Med zgornjimi štirimi sta najboljši prvi dve (z oceno 12). Kot vidimo iz tretje alineje, je možna rešitev tudi ta, da niza sploh ne razbijemo na več krajših.

Obrazec za oddajo rešitev

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

Datoteka s tvojo rešitvijo:

Najboljše doslej oddane rešitve

Prikaži podrobno tabelo rezultatov po posameznih testnih primerih.

Skupni seštevek

V skupnem seštevku se za vsakega tekmovalca seštejejo njegove točke z vseh testnih primerov.

Ime in priimekRezultat
Miloš Ljubotina91
Samo Kralj79
Domen Hočevar74
Matej Kralj70
Gregor Kikelj50

[H kazalu. | Na vrh te strani. | Imate vprašanje ali komentar?]