TREENINGVÕISTLUS (ACM ICPC meeskond vs IOI meeskond) 22.11.1997 1. NELINURGAD ABCD on kumer nelinurk, mille diagonaalide lõikepunkt I ei asu nelinurga küljel. Olgu teada mingi hulk nende punkide poolt moodustatud lõikude võrdusi. Leida, kas antud võrdustest järeldub otsitav võrdus. Sisendfaili esimesel real on teadaolevate võrduste arv, järgnevad ühekaupa real kõik need võrdused. Viimasel real on võrdus, mille järeldumist eelmisest tuleb kontrollida. Väljunfaili kirjutada "Järeldub" või "Ei järeldu". Näited: 2 2 AD=BC AI=BI AB=CD AB=CD AI=IC CI=ID Järeldub Ei järeldu 2. OPTIMAALNE ARVUTAMINE Antud: avaldis, mis sisaldab ühte ladina väiketähega tähistatud muutujat, sulge ja tehtemärke + ja *. Korrutamine on alati tähistatud märgiga *. Avaldise väärtuse arvutamiseks peab õpilane tegema ühekaupa tehteid, liites või korrutades omavahel juba olemasolevaid suurusi (muutuja väärtus või juba leitud vahetulemused). Konstandi liitmine või konstandiga korrutamine pole lubatud. Leida minimaalne vajalik tehete arv ja järjestikused tehted. Sisendfaili ainsal real on avaldis pikkusega kuni 80 sümbolit. Väljundfaili esimesele reale kirjutada vajalik tehete arv, järgmistele ridadele tehted ja tehete tulemused, kirjutades vajadusel astmed sümboli ^ abil. Näide: (a+a+a+a+a+a)*(a+a+a) 6 a+a=2a 2a+a=3a 3a+3a=6a 3a*6a=18a^2 3. SUHTLEVAD LAEVAD Kalalaevade flotill püüab saarestikus kala. Laevad on suutelised omavahel suhtlema, kuid vahetevahel peavad seda tegema teiste laevade abiga, sest suhtlemiseks on vaja otsenähtavust ja laevade vahel asuvad saared reeglina takistavad otsest sidet. Sisendandmed Tekstifaili LAEVAD.IN esimesel real on antud saarte arv M ja laevade arv N. Järgneval M real on saarte andmed kujul X-koordinaat Y-koordinaat Raadius ja edasi N järgneval real laevade asukoha andmed kujul Laeva_tähis X-koordinaat Y-koordinaat Viimasel real on nende kahe laeva tähised, mis tahavad omavahel suhelda. Laevad tähised on unikaalsed kahetähelised stringid, mis koosnevad suurtest ladina tähtedest. Kõik koordinaadid ja raadiused on reaalarvud. Kahe laeva vahel on otsenähtavus, kui nende laevad vaheline sirge ei oma saarega ühiseid punkte. Väljundandmed Tekstifaili LAEVAD.OUT esimesele reale tuleb kirjutada suhtlemises osalevate laevade arv ja teisele reale laevade tähised signaali liikumise teel. Näide LAEVAD.IN 3 5 3 3 1 1 3 1 5 3 1 AA 1 1 BB 1 5 CC 5 5 DD 5 1 EX 9.2 3 AA BB LAEVAD.OUT 5 AA DD EX CC BB 4. LOOMADE TRANSPORT (testi aeg: 10 sek) Farmis A elab farmer, kellel on loomade veoks sobiv veoauto. Kui naaberfarmidel on vaja teostada loomade transporti ühest farmist teise, siis tellitakse see teenus farmist A. Ümbruskonna farme tähistatakse tähtedega A, B, C, D, E, F ja G ning nende farmide omavahelised kaugused on esitatud järgmises tabelis: B C D E F G A 56 43 71 35 41 36 B . 54 58 36 79 31 C . . 30 20 31 58 D . . . 38 59 75 E . . . . 44 67 F . . . . . 72 Iga kord, kui on kogunenud mõned tellimused loomade veoks, peab farmer otsustama, millises järjekorras vedusid teha, et läbisõidetav maa oleks lühim. Arvestada tuleb tal järgmiste asjaoludega: 1) veoauto alustab oma teekonda alati farmist A ja peab lõpuks sinna tagasi jõudma; 2) veoautosse mahub korraga ainult üks lehm; 3) kõik tellimused on antud kui farmitähiste paarid, alustades selle farmi tähisega, kust lehm on vaja peale võtta ja lõpetades selle farmi tähisega, kuhu lehm on vaja viia. On vaja kirjutada programm, mis antud hulga tellimuste korral teeks kindlaks lühima marsruudi, millega saaks kõik tellimused rahuldatud ja mis arvestaks eespool loetletud piirangutega. Sisendandmed Tellimused on salvestatud tekstifaili LOOMAD.IN. Esimesel real on tellimuste arv N (1 <= N <= 10). Järgneval N real on tellimused esitatud kahe tühikuga eraldatud tähe abil, kusjuures esimene täht tähistab veo alguspunkti ja teine täht veo lõpp-punkti. Väljundandmed Tekstifaili LOOMAD.OUT esimesele reale tuleb kirjutada lühima marsruudi pikkus ja teisele reale marsruudil paiknevate farmide tähised nende farmide läbimise järjekorras. Näide: LOOMAD.IN 5 F C G B B D A E G A LOOMAD.OUT 368 A E F C G B D G A 4. DOOMINO N-doomino kivide komplekt koosneb ristkülikukujulistest kividest mõõtmetega 2x1 ühikut, mis on jagatud kaheks ruudukujuliseks pooleks ja mille kummalgi poolel on üks number vahemikust 0...N. Iga võimalik kivi esineb komplektis täpselt üks kord. Doominokive asetatakse lauale nii, et alates teisest kivist omab iga kivi üks pool ühist serva eelmise kivi ühe poolega ja need ühist serva omavad pooled on sama numbriga. Kui kivi omab ühiseid servi kahe naabriga, peavad need servad olema antud kivi erinevatest pooltest. N-doomino kõik kivid on laotud ristkülikukujulisele alale mõõtmetega KxM ja täidavad selle ala täpselt. On teada, et laotud kivid moodustavad õiges järjekorras lugedes ahela, milles kehtib eelmises lõigus toodud ladumise tingimus. Leida üks selline ahel. Sisend: Faili INPUT.TXT esimesel real on tühikutega eraldatud täisarvud N (1 <= N <= 9), K ja M. Faili järgmisel K real on igaühel M tühikutega eraldatud arvu, mis on kivide pooltel olevad numbrid. Väljund: Faili OUTPUT.TXT K esimesele reale kirjutada igaühele M tühikutega eraldatud arvu nii, et iga kivi mõlema poole numbrite asemel on selle kivi järjekorranumber leitud ahelas. Näide: INPUT.TXT OUTPUT.TXT 2 3 4 1 1 2 2 1 1 1 2 5 6 6 3 0 0 1 2 5 4 4 3 0 0 2 2 6. TASAKAALUKAS ARITMEETIKA Balansseeritud N-süsteemiks nimetatakse positsioonilist arvusüsteemi paaritul alusel N, mille numbrite väärtused on -N/2, -N/2+1, ..., 0, ..., N/2-1, N/2. Näiteks balansseeritud 3-süsteemi numbrite väärtused on -1, 0 ja 1 (tähistatakse enamasti -, 0 ja +) ning balansseeritud 3-arvu +0-0 väärtus tavalises 10-süsteemis on (+1)*3^3 + 0*3^2 + (-1)*3^1 + 0 = 27 - 3 = 24. Kirjutada programm, mis sisestab suvalises balansseeritud N-süsteemis (3 <= N <= 99) antud kuni 100-kohalised arvud ja väljastab nende summa ja korrutise samas süsteemis. Sisend: Faili INPUT.TXT esimesel real on balansseeritud N-süsteemi numbrid väärtuste kasvamise järjekorras, teisel real esimene ja kolmandal real teine operand. Väljund: Faili OUTPUT.TXT esimesele reale kirjutada antud operandide summa ja teisele nende korrutis. Võib eeldada, et kumbki tulemus ei ole pikem kui 100-kohaline. Näide: INPUT.TXT OUTPUT.TXT {[|]} {{]}] ]|[ {[{[}{{ {{|}}