BOI/IOI VALIKVÕISTLUS 12.04.1998 1. KOODLUKU AVAMINE 30 punkti 10 sekundit Politseil õnnestus avastada ühe allilmaliidri arhiiv. Kahjuks on arhiivi kõige huvitavamad dokumendid suletud seifi, mida kaitseb koodlukk. Selleks, et dokumendid kätte saada enne kui mafioosod arhiivi avastamisest kuulevad ja maalt lahkuvad, on vaja lukk võimalikult kiiresti avada. Luku avamiseks on vaja seifi uksel asuva klaviatuuri abil sisestada kood. Luku ehitus on selline, et ta mäletab alati N viimati sisestatud sümbolit ja avaneb kui need langevad kokku tema N-sümbolilise koodiga. Selleks, et lukk vähima võimaliku ajaga lahti saada, tuleb leida lühim klahvivajutuste jada, mis sisaldab kõiki võimalikke koode. Sisend: Tekstifaili KOOD.SIS esimesel real on kõik koodluku klaviatuuril leiduvad märgid (suured ja väikesed ladina tähed ja numbrid, kokku 1 kuni 60 erinevat sümbolit) ja teisel real luku avamiseks vajaliku koodi pikkus (täisarv N, 1 <= N <= 30). Väljund: Tekstifaili KOOD.VAL esimesele reale väljastada lühim võimalik klahvivajutuste jada, mis garanteeritult luku avab (st lühim sõne, mis sisaldab alamsõnedena kõiki N-sümbolilisi jadasid luku klaviatuuril leiduvatest märkidest). Näide: KOOD.SIS KOOD.VAL abc aabbccacba 2 Hindamine: Lahendus, mis garanteeritult luku avab, saab testi eest M/K selle testi punktidest, kus M on vähim võimalik väljundjada pikkus ja K on hinnatava programmi leitud jada pikkus. Programm, mille väljastatud jada mõnda koodi ei sisalda või sisaldab lubamatuid sümboleid, saab testi eest loomulikult 0 punkti. Testimisel kasutatakse sisendandmeid, mille korral leidub lahendus pikkusega mitte üle 200 000 sümboli. 2. KAS JAGUB? 30 punkti 10 sekundit Vaatleme N naturaalarvulist tundmatut X1, X2, ..., X9, X10, ..., XN, kus 1≤N≤30 ja on teada, et arvud Xi rahuldavad võrratust 1 <= Xi <= 2000000000 (st on kujutatavad 32-bitiste täisarvudena). Tähistagu A»B väidet "arv A jagub arvuga B" (sümboli » ASCII kood on 175). On antud teatud arv väiteid kujul Xi»Xj või Xi»A, kus A on mingi naturaalarv (1 <= A <= 2000000000). Leida iga tundmatu Xi jaoks maksimaalne naturaalarv M, mille kohta saab väita, et Xi»M. Sisend: Tekstifaili JAGAB.SIS esimesel real on tundmatute arv N ja jaguvusväidete arv K (K <= 1000). Järgnevatel K real on igaühel üks jaguvusväide. Väljund: Kirjutada faili JAGAB.VAL N rida, kus i. real on muutuja Xi kohta saadud tulemus kujul Xi»M. Näide: JAGAB.SIS JAGAB.VAL 3 3 X1»4 X1»4 X2»12 X2»6 X3»1 X2»X1 3. HANOI TORN MARKOVI MOODI 30 punkti 200000 takti Elektroonikakontsern NiPhiggah on valmis saanud täiesti uut liiki protsessori, mille aluseks pole mitte Turingi masin, vaid Markovi normaalalgoritm. Revolutsioonilise protsessoripere esimesel mudelil on ainult üks register ja tema käsustikus ainult üks käsk, mis toimib alati protsessori ainukesel registril. Käsul on kaks operandi: esimene neist on string, mida registrist otsitakse ja teine string, millega see asendatakse. Programm sellel protsessoril koosneb käskudest kujul (L,R), kus L ja R on stringid, mis ei sisalda sulge ega koma. Enne programmi täitmise algust loetakse sisendandmeteks olev string protsessori ainsasse registrisse. Programmi täitmine algab selle esimesest käsust. Kui otsitav string L1 on registri väärtuse alamstring, siis asendatakse selle vasakpoolseim esinemine stringiga R1 ja alustatakse programmi täitmist algusest. Kui stringi L1 registris ei esine, jätkatakse programmi täitmist teisest käsust. Kui L2 on registri väärtuse alamstring, siis tehakse asendus ja jätkatakse jälle programmi esimesest käsust, muidu minnakse järgmisele käsule jne. Programmi töö on lõppenud, kui enam asendusi teha ei saa. Programmi väljundiks on protsessori registri lõppväärtus. Programmeerija mugavus huvides ignoreerib protsessor kõiki käskude vahel olevaid sümboleid, seega võib käsud soovi korral kirjutada eraldi ridadele ja lisada nende vahele ka kommentaare. Loomulikult ei tohi kommentaarid sisaldada sulge. Näiteks programmi (0++,1)(1++,++0)(++,1) rakendamisel sisendile 1011++ saame registris väärtuste jada 1011++, 101++0, 10++00, 1100. Pole ilmselt raske taibata, et see programm suurendab kahendarvu ühe võrra. Kontsern NiPhiggah tahab oma uue protsessori demonstreerimiseks saada programmi, mis lahendab Hanoi torni ülesannet. Sisend: Hanoi torni ülesannet lahendava programmi sisendiks on string kujul 1****3, kus tärnide arv näitab vardalt 1 vardale 3 viidavate ketaste arvu (1 kuni 10). Kettad on alati vaja viia vardalt 1 vardale 3, varrast 2 võib kasutada abivardana. Väljund: Programmi väljundiks peab olema ketaste ümberpaigutamiste jada, kus ketta viimist vardalt A vardale B tähistatakse paariga AB. Kõik ümberpaigutused kirjutatakse vahetult üks-teise järele. Kuna NiPhiggah tahab oma uuest protsessorist võimalikult head muljet jätta, siis peab programm leidma optimaalse (so vähima võimaliku tõstmiste arvuga) lahenduse. Näide: sisend väljund 1***3 13123213212313 Hindamine: Selle ülesande lahenduseks on protsessori NiPhiggah käskudest koosnev tekstifail, mis testimiseks käivitatakse zhürii kirjutatud NiPhiggah-protsessori emulaatoris ja hinnatakse saadud väljundit. Emulaator suudab töödelda käske, mille pikkus ei ületa 1024 sümbolit ja tema registri suurus on 10240 sümbolit. Lahenduse aega mõõdetakse protsessoritaktides (käsu täitmine võtab aega ühe takti, ükskõik, kas asendamine toimub või mitte).