PROGRAMMEERIMISOLÜMPIAADI PIIRKONDLIK VOOR 07.02.1998 NOOREM RÜHM (kuni 10. klass) 1. NAKKUSHAIGUS 30 punkti 5 sekundit Nakkushaiguse leviku uurimiseks kontrolliti teatud grupi liikmeid nakatumise suhtes ja märgiti üles kõik teised grupiliikmed, kellega nad suhelnud on. Eesmärgiks oli välja selgitada isikud, kes on küll nakkusega kokku puutunud, kuid nakatunud ei ole. Sisend: Tekstifaili INPUT.TXT esimesel real on uuritud isikute arv N (1 <= N <= 5000) ja järgmisel N real igaühel ühe isiku andmed - tühikutega eraldatud täisarvud. Esimene arv real on 0, kui isik ei ole nakatunud ja 1, kui isik on nakatunud, teine arv Ki (0 <= Ki <= 500) on isiku kontaktide arv, millele järgnevad Ki täisarvu - nende isikute järjekorranumbrid, kellega antud isik kokku puutus (kõik uuritavad isikud on nummerdatud alates 1st). Väljund: Tekstifaili OUTPUT.TXT väljastada nende isikute andmed, kes on nakatunutega kokku puutunud, kuid pole ise haigestunud. Iga isiku andmed väljastada eraldi reale, kusjuures esimene arv real peab olema isiku järjekorranumber, teine arv näitama nende nakatunute arvu, kellega antud isik kokku puutus ja edasi nende nakatunute järjekorranumbrid. Ridade järjekord failis ega isikute järjekord real pole olulised. Näide: INPUT.TXT OUTPUT.TXT 5 1 2 2 5 0 3 2 5 4 4 1 5 1 2 3 1 1 1 2 0 2 5 1 1 2 1 4 2. RISTKÜLIKUTE LEIDMINE 30 punkti 5 sekundit Kirjutada programm, mis leiab antud punktihulgast kõik sellised nelikud, mis moodustavad koordinaattelgedega paralleelsete külgedega ristkülikud. Sisend: Tekstifaili INPUT.TXT esimesel real on punktide arv N (1 <= N <= 100) ja järgmisel N real igaühel 2 tühikutega eraldatud täisarvu Xi ja Yi: punkti i koordinaadid (|Xi| < 100, |Yi| < 100). Kõik punktid on erinevad. Väljund: Tekstifaili OUTPUT.TXT väljastada igale reale 4 tühikutega eraldatud täisarvu: ristküliku tippudeks olevate punktide järjekorranumbrid sisendfailis. Iga ristkülik esitada ainult ühes eksemplaris. Punktide esitamine teises järjekorras ei ole uus ristkülik. Ristkülikute esitamise järjekord failis ega punktide esitamise järjekord real pole olulised. Näide: INPUT.TXT OUTPUT.TXT 6 1 2 4 5 10 10 1 3 4 6 10 20 2 3 5 6 10 30 30 10 30 20 30 30 3. ROOMA NUMBRID 40 punkti 5 sekundit Vanad roomlased kasutasid arvude kirjutamiseks suuri ladina tähti järgmistes tähendustes: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Üldjuhul on selles süsteemis kirjutatud arvu väärtuseks kasutatud sümbolite väärtuste summa (näiteks XXV=10+10+5). Erandiks on juht, kui väiksema väärtusega sümbol on suurema väärtusega sümbolist vasakul; sellise paari väärtuseks on sümbolite väärtuste vahe (näiteks IX=10-1=9, CXC=100+(100-10)=190). Lahutada tohib ainult sümboleid I, X ja C ning lahutamine on alati kõige parempoolsemas võimalikus liikmes (st XXIX ja mitte XIXX). Kirjutada programm rooma numbritena esitatud arvude teisendamiseks kümnendsüsteemi. Sisend: Tekstifaili INPUT.TXT ainsal real on rooma kirjaviisis esitatud täisarv. Väljund: Tekstifaili OUTPUT.TXT esimesele reale väljastada sisendis olev arv 10-süsteemis. Näide: INPUT.TXT OUTPUT.TXT MMCMXXIV 2924 VANEM RÜHM (11.-12. klass) 1. TEISE ASTME KONTAKTID 30 punkti 5 sekundit Nakkushaiguse leviku uurimiseks jagati katsealused kolme gruppi. A-grupis on isikud, kes on antud haigusesse nakatunud. B-grupi liikmete hulgas korraldati küsitlus ja tehti kindlaks, milliste A-grupi liikmetega nad on kokku puutunud. C-grupi liikmete hulgas korraldati samuti küsitlus ja tehti kindlaks, milliste A- ja B-grupi liikmetega nad on kokku puutunud. Eesmärgiks on välja selgitada sellised C-grupi liikmed, kes ei ole otseselt kokku puutunud ühegi A-grupi liikmega, aga on kokku puutunud B-grupi liikmega, kes omakorda on kokku puutunud A-grupi liikmega. Sisend: Tekstifaili INPUT.TXT esimesel real on kolm täisarvu NA, NB ja NC (1 <= Ni <= 1000), mis näitavad vastavate gruppide suurusi, teisel real küsitlustes tuvastatud kontaktide koguarv N (1 <= N <= 10000) ja järgmisel N real kontaktide info kujul Gi Gj, kus G on grupi tähis (A, B või C) ning i ja j on vastavate isikute järjekorranumbrid oma grupis (iga grupi liikmed on nummerdatud alates 1st). Väljund: Tekstifaili OUTPUT.TXT väljastada iga otsitava isiku kohta rida kujul Ck Bj Ai, kus Ck on otsitav C-grupi liige ja Bj ning Ai näitavad ühte teise astme kontakti (ühel C-grupi liikmel võib olla rohkem kui üks teise astme kontakt). Ridade järjekord väljundfailis pole oluline. Näide: INPUT.TXT OUTPUT.TXT 2 2 3 C2 B1 A1 5 C3 B2 C1 A2 B1 A1 C1 B1 C2 B1 2. RISTKÜLIKUTE LEIDMINE 30 punkti 5 sekundit Kirjutada programm, mis leiab antud punktihulgast kõik sellised nelikud, mis moodustavad ristkülikud. Sisend: Tekstifaili INPUT.TXT esimesel real on punktide arv N (1 <= N <= 100) ja järgmisel N real igaühel 2 tühikutega eraldatud täisarvu Xi ja Yi: punkti i koordinaadid (|Xi| < 100, |Yi| < 100). Kõik punktid on erinevad. Väljund: Tekstifaili OUTPUT.TXT väljastada igale reale 4 tühikutega eraldatud täisarvu: ristküliku tippudeks olevate punktide järjekorranumbrid sisendfailis. Iga ristkülik esitada ainult ühes eksemplaris. Punktide esitamine teises järjekorras ei ole uus ristkülik. Ristkülikute esitamise järjekord failis ega punktide esitamise järjekord real pole olulised. Näide: INPUT.TXT OUTPUT.TXT 6 1 2 5 6 1 1 1 3 4 5 3 1 0 2 2 2 1 3 3 3 3. ROOMA NUMBRID 40 punkti 5 sekundit Vanad roomlased kasutasid arvude kirjutamiseks suuri ladina tähti järgmistes tähendustes: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Üldjuhul on selles süsteemis kirjutatud arvu väärtuseks kasutatud sümbolite väärtuste summa (näiteks XXV=10+10+5). Erandiks on juht, kui väiksema väärtusega sümbol on suurema väärtusega sümbolist vasakul; sellise paari väärtuseks on sümbolite väärtuste vahe (näiteks IX=10-1=9, CXC=100+(100-10)=190). Kirjutada programm kümnendsüsteemis esitatud arvude teisendamiseks rooma süsteemi. Sisend: Tekstifaili INPUT.TXT ainsal real on 10-süsteemis esitatud täisarv N (1 <= N <= 3999). Väljund: Tekstifaili OUTPUT.TXT esimesele reale väljastada sisendis olev arv rooma süsteemis. Väljund peab rahuldama järgmisi tingimusi: 1) sümboleid I, X, C ja M ei kirjutata üle kolme, sümboleid V, L ja D üle ühe järjest; 2) lahutada tohib ainult sümboleid I, X ja C; 3) lahutada tohib ainult juhul, kui see on vajalik, et vältida reegli 1) rikkumist; 4) lahutamiste arv peab olema minimaalne võimalik; 5) lahutamine peab olema alati kõige parempoolsemas võimalikus positsioonis. Näide: INPUT.TXT OUTPUT.TXT 2924 MMCMXXIV