26. juuni 1993. a.

IOI kandidaatide katsevõistluse ülesanded

1. VÕRRANDISÜSTEEMIDE LAHENDAMINE. ( 30 p. )

Programmeerida instrument reaalarvuliste kordajatega kolme tundmatuga 3 lineaarvõrrandist koosnevate süsteemide lahendamiseks.

Võrrandid sisestatakse kasutaja valitud tekstifailist (soovi korral klaviatuurilt) stringidena, näiteks

5.2x+2.5y-z=3
y+z=12
1.234x+y-4.23z=-3.9

Lubatud muutujad on x,y ja z. Kõik reaalarvud ümardada täpsuseni 3 kohta peale koma. Võrrandite süntaksi kontroll pole vajalik.

Võrrandid kirjutatakse sisestamise järel järgmistele vabadele ridadele ja kasutaja saab moodustada uusi võrrandeid, kirjutades võrrandi numbri järele eeskirja üheks järgmistest operatsioonidest:

1. võrrandi korrutamine arvuga,

2. kahe võrrandi liitmine,

3. võrrandi jagamine arvuga.

Võrrandid võiks lahendamise ajal olla kujutatud järgmiselt:

#1:           5.2x+2.5y-z=3
#2:           y+z=12
#3:           1.234x+y-4.23z=-3.9     {esialgsed võrrandid}
#4=#1+#2:     5.2x+3.5y=15
#5=#2*4.23:   4.23y+4.23z=50.76
#6=#3+_                              {uue eeskirja sisestamine}

Võib eeldada, et süsteemi lahendus mahub ekraanile. Kui kõik tundmatud on avaldatud, väljastada vastus.

2. DOOMINO JAGAMINE ( 30 p. )

Kirjutada programm, mis loeb tekstifailist või klaviatuurilt andmed N doominokivi kohta ja leiab, mitu sellist doominojada saab nendest kividest maksimaalselt moodustada, mida enam omavahel otsapidi ühendada ei saa. Näiteks kividest

0:3, 1:3, 2:3, 3:3 ja 4:3

saab moodustada kolm jada: 0:3+3:1, 2:3+3:4 ja 3:3.

Tekstifailis on kirjes ühe kivi punktid, näiteks '0 3'. Kontrollida ka andmete korrektsust.

Koos vastusega väljastada ka üks maksimaalne ridade komplekt.

3. TALLINN - BUENOS AIRES. ( 30 p. )

Olgu lennujaamad kodeeritud numbritega 1..N (N<=50), millest nr.1 on Tallinn ja nr.N Buenos Aires. Olgu M lennuliini kohta (M<="1000)" teada 1)alguspunkt, 2)lõpp-punkt, 3)pileti hind dollarites (täisarv).

Kirjutada programm, mis loeb kasutaja poolt valitud tekstifailist või klaviatuurilt arvud N ja M ning andmed liinide kohta ja leiab, kas ja kui odavalt on võimalik olümpiaadile sõita.

Faili esimeses kirjes on N ja M (näiteks '50 1000'), edasi ühe liini kaupa (näiteks '1 22 170').

Koos positiivse vastusega väljastada ka optimaalne marsruut liinikirjete kaupa.

4. PUNKTIDE PAIGUTAMINE ( 100 p. )

Programm jagab tekstiekraani osadeks vastavalt joonisele.

                                      61.pos.
┌──────────────────────────────────────┬───────────────┐
│                                      │ Sisestage     │
│    B(11,3)  A(12,3)                  │ punkt:        │
│           **D(12,3)                  │  E(54,_       │
│                *C(16,4)              │               │
│                                      ├───────────────┤9.rida
│                                      │ A(12,3)       │
│                                      │ B(11,3)       │
│                                      │ C(16,4)       │
│                                      │ D(12,3)       │
│                                      │               │
│                                      │               │
└──────────────────────────────────────┴───────────────┘

Parempoolses ülemises osas toimub dialoog, kus kasutaja sisestab ühekaupa punktide tähiseid (suured tähed) koos koordinaatidega, näiteks E(54,21).

Kui koordinaadid kuuluvad ekraani vasakusse ossa, siis kirjutatakse sisestatud string paremasse alumisse ossa, punkt paigutatakse sümbolina * oma kohale ja tema juurde kirjutatakse samuti tähis koos koordinaatidega.

Punkti kirjed tuleb paigutada nii, et nad ei kata tärne ega teisi kirjeid. Kirje üks ots peab paiknema ühes vastava tärni kaheksast naaberruudust, kumbki ots ei tohi olla ühegi teise tärni naaberruudus (kirje keskmised sümbolid võivad). U"he tärni juures võib olla mitu kirjet. Kui vaja, tuleb punkti sisestamise järel ka teiste punktide kirjed ümber paigutada. Kui tingimustele vastavat paigutust ei leidu, anda dialoogiaknas vastav teade.

Sama tähisega punkti korduvat sisestamist vaadelda punkti ümbertõstmisena.