Da li je iko rijesio ovaj zadatak - Sef?

Pitanja i problemi
1

Da li je iko uspio da rijesi do kraja ovaj zadatak? Prvih par inputa moze da se rijesi, ali kada se dodje do inputa 4 (sef.04.in) kompleksnost postaje prevelika…

https://takprog.dms.rs/takmicenja/2005.3.sav/6.sef/task.html

2

izgleda kao da i sam testni primer nije dobar. deluje mi da šifra aaab može da bude rešenje.

3

tacno, za taj prvi je “aaab”.

Ali i pored toga, izgleda kao da zadatak ne moze da se odradi 100%.

4

Ovo nije zadatak standardnog tipa – ne ocekuje se da takmicari napisu jedan program i predaju ga, i da se taj program onda izvrsava sa vremenskim ogranicenjem na komisijskom sistemu. Umesto toga, ovo je “output-only” zadatak: svi primeri su dati unapred tokom takmicenja, i treba samo predati deset izlaznih fajlova. Kako cete doci do tih izlaza je vasa stvar, ali obicno je dobra ideja pogledati kako primeri izgledaju, jer nece isti pristup resiti sve.

Konkretno, u ovom slucaju, sef.04.in ima sledecu strukturu:

  • 26 ???...??: sifra ima 26 karaktera (tacnije, posto se u ostalim redovima pojavljuju sva slova, sadrzi svako slovo po jednom)
  • 5 *a*n*: slovo a se nalazi pre n
  • 5 *i*x*: i se nalazi pre x
  • …

Ovaj primer se moze resiti tako sto ga posmatramo kao graf gde su cvorovi slova, a grana od u do v znaci da u dolazi pre v. Validna sifra je onda topolosko sortiranje cvorova u grafu.

2 Likes
5

to vec ima smisla :slight_smile:

Vidim da za ovaj zadatak jedino nema resenja na sajtu (pretpostavljam zbog toga sto svaki primjer ima drugaciji pristup). Takodje mi je cudno sto neki fajlovi imaju patterne sa vise zvjezdica ("*?****") kada je ovo u stvari jednako ("*?*"). Mozda je ovo takodje dato da takmicari optimizuju prije rjesavanja ili sl.

6

Vidim da za ovaj zadatak jedino nema resenja na sajtu

Bas tako, zadatak se ne resava samo jednim programom a tada je najcesce bila praksa da se objavi samo kod resenja bez analize zadatka, sto za ovaj zadatak bas i nema smisla.

Mozda je ovo takodje dato da takmicari optimizuju prije rjesavanja ili sl.

Da, ** je tu verovatno samo da bi bilo malo vise posla u zadatku (a i resenje primera 5, gde ulazi sadrze samo ? i *, bi bilo potpuno ocigledno bez ovoga).