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).
- Kratek opis naloge na tej strani.
- Podroben opis naloge in oblike vhodnih ter izhodnih datotek.
- Vhodne datoteke.
- Registracija (preden lahko oddajaš svoje rešitve).
- Obrazec za oddajo tvojih rešitev.
- Najboljši doslej oddani rezultati za posamezni testni primer.
- Razvrstitev tekmovalcev v skupnem seštevku.
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:
- k + anet + k + an + anet z oceno (1 + 4 + 2) + 5 = 12;
- kan + et + kan + an + et z oceno (3 + 2 + 2) + 5 = 12;
- kanetkananet z oceno (12) + 1 = 13;
- k + ane + tkan + ane + t z oceno (1 + 3 + 4 + 1) + 5 = 14.
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.
- Podrobnejši opis naloge ter vhodnih in izhodnih datotek.
- Vhodne datoteke.
- Registracija.
Obrazec za oddajo rešitev
(Oddaja rešitev je možna do vključno 27. marca 2020.)
Najboljše doslej oddane rešitve
Skupni seštevek
V skupnem seštevku se za vsakega tekmovalca seštejejo njegove točke z vseh testnih primerov.
| Ime in priimek | Rezultat |
|---|---|
| Miloš Ljubotina | 91 |
| Samo Kralj | 79 |
| Domen Hočevar | 74 |
| Matej Kralj | 70 |
| Gregor Kikelj | 50 |
[H kazalu. | Na vrh te strani. | Imate vprašanje ali komentar?]