ACM RTK - 2. skupina

Sumljiva imenovanja

Pravkar ustanovljena Komisija za nadzor zaposlovanja v javni upravi dobiva številne vloge za oceno zakonitosti imenovanja novih uradnikov. Vsaka vloga je sestavljena iz treh stvari: seznam kvalifikacij, ki so zahtevane za to delovno mesto; seznam kvalifikacij, ki jih je imel človek, ki je to delovno mesto dobil; nato pa še seznami kvalifikacij vseh ostalih kandidatov, ki so se potegovali za to delovno mesto, vendar ga niso dobili.

Komisija mora za vsako imenovanje ugotoviti, ali je zakonito, sumljivo ali celo nezakonito. Pri tem uporablja naslednja pravila:

• imenovanje je nezakonito, če kandidat nima vseh kvalifikacij, zahtevanih na tem delovnem mestu;
• imenovanje je sumljivo, če kandidat sicer ima vse potrebne kvalifikacije, vendar obstaja boljši kandidat; torej kandidat, ki ima vse kvalifikacije kot tisti, ki je bil imenovan, in še kakšno zraven;
• sicer je imenovanje zakonito.

Napiši program, ki prebere vlogo in izpiše, ali je bilo imenovanje nezakonito, sumljivo ali zakonito.

Vhodni podatki: privzemimo, da obstaja natanko n (za nek n ≤ 32) možnih kvalifikacij. Tako lahko seznam zahtevanih kvalifikacij podamo kar z nizom oblike: s = c₁c₂c₃ ... c_n−1c_n, kjer je lahko vsaka izmed črk c_i le D ali N in kjer črka D na i-tem mestu pomeni, da je i-ta kvalifikacija zahtevana, črka N pa, da ni. Na primer, niz DNDNDNNNDDDNNDNDNDNNDNNNDDDNNDNN predstavlja delovno mesto, kjer so zahtevane kvalifikacije št. 1, 3, 5, 9, 10, ..., kvalifikacije št. 2, 4, 6, 7, 8, ... pa ne. Podobno predstavimo seznam kvalifikacij, ki jih imajo kandidati. Tako kot prej črka D na i-tem mestu pomeni, da kandidat i-to kvalifikacijo ima, črka N pa, da je nima.

Tvoj program lahko vhodne podatke bere s standardnega vhoda ali pa iz datoteke vhod.txt (kar ti je lažje). V prvi vrstici je niz, ki predstavlja zahtevane kvalifikacije za delovno mesto; druga vrstica predstavlja kvalifikacije kandidata, ki je bil zaposlen; vse naslednje vrstice pa predstavljajo kvalifikacije vseh ostalih kandidatov.

Tvoja rešitev naj deluje tudi v primerih, ko je število vrstic v vhodni datoteki zelo veliko — preveliko, da bi celotno vsebino vhodne datoteke naenkrat shranili v pomnilnik.

Predpostaviš lahko, da obstaja funkcija vStevilo(s), ki spremeni niz kvalifikacij s v število, ki ima v binarnem zapisu na i-tem mestu 1, če je imel niz kvalifikacij tam črko D in 0, če je bila tam črka N. Ni pa nujno, da to funkcijo uporabiš (nalogo lahko čisto dobro rešiš tudi brez nje).

Izhodni podatki: izpiši, ali je bilo imenovanje nezakonito, sumljivo ali zakonito.

Primer vhodne datoteke:

NNDDDDDDNDDNDNNDNDDDNNDNDNNNDDNN
DDDDDDDDNDDDDDDDDDDDNDDDDDDDDDNN
DDDDDDDDNDDDDDDDDDDDDDDDDDDDDDND
NDNNDDDNNNNNNDNNNNDNDNNDDNNDNNNN
NNNNNDNDNDDNNDDNDNNNDNDNDDNDDDDD
NNNDDNDNDNDDDNDDDNNNNDDDDDNNNDND
NDDDDNNNDNNNNDDNNNNNNDNNNDNNDNDN
NNDDDNDDNDDNNDDDDDDNDDDDNNNDDDNN
NNNNNDNDNDDDNDNDDNDNDNNNNDNDNNNN
NDDDNNNDDDNNDNDDNNNDNDDDNNDNNNND
NNNNDNDDDDDDNNDNNDDDDDDNDNDNNDDN

Pripadajoč izpis:

sumljivo

(Pojasnilo: drugi kandidat ima vse kvalifikacije, ki jih ima prvi, in še dve taki, ki ju prvi nima, zato je imenovanje sumljivo.)