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

Najkrajši skupni nadniz

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 24. marca 2017 (dan pred tekmovanjem).

Opis naloge

Danih je več nizov, ki jih sestavljajo male črke angleške abecede. Naloga je poiskati kakšen čim krajši niz, v katerem se kot podnizi pojavljajo vsi dani vhodni nizi. Z drugimi besedami torej iščemo čim krajši skupni nadniz vseh vhodnih nizov. Pri tem so dovoljene tudi take pojavitve podnizov, v katerih se črke podniza ne pojavljajo strnjeno skupaj (na primer: niz aaa je podniz niza ananas).

Primer: recimo, da imamo vhodne nize miza, zima in mazivo. Nekaj primernih nizov, ki so skupni nadnizi vseh treh vhodnih nizov, je na primer:

Izkaže se, da je 9 znakov pri tem konkretnem primeru najboljša možna rešitev — noben skupni nadniz vseh treh vhodnih nizov ni krajši od 9 znakov.

Obrazec za oddajo rešitev

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

Datoteka s tvojo rešitvijo:

Najboljši doslej oddani razporedi

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
Uroš Koritnik486
Bor Grošelj Simić444
Franci Obid414
Tomaž Martinčič383
Gregor Kikelj333
Andrej Golčer286
Blaž Zupančič277
Martin Prelog148
Amon Stopinšek78
Nejc Šuklje60
Matevž Rom10
Žan Pust1

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