XL, 1992.-1993. õppeaasta

Koduse eelvooru ülesanded

Koolinoorte vabariiklikul informaatikaolümpiaadil oli tänavu nagu eelmiselgi aastal kaks vooru: kodune eelvoor ja lõppvoor, mis toimus Tartus 28. märtsil 1993. a. Kõik osavõtjad võistlesid ühes klassis.

Informaatikaolümpiaadist osavõtt põhineb suurel määral õpilaste enda entusiasmil. Vähestes koolides on tugevad arvutiõpetajad ja korralikud arvutiklassid. Samuti pole ka väljakujunenud olümpiaadide süsteemi: koolis, linnas/maakonnas, vabariigis. Sellele vaatamata oli osavõtt üllatavalt rohkearvuline. Paistab, et huvi arvutite ja programmeerimise vastu õpilastel on. Olümpiaadikomisjonile saabus 113 tööd, millest suur osa näitas arvestatavat programmeerimisoskust. Natuke kurb on, et proovijate hulgas oli ainult kaks tütarlast.

1. ülesanne

Antud: reaalarvud A, B, C, D, U ja V.

Leida: Funktsiooni y = Ax³ + Bx² + Cx + D minimaalne ja maksimaalne väärtus lõigul [U,V].

Siin ei saa lugeda õigeks "programmeerijalikku lahendust", kus mingi sammu kaupa paigutatakse lõigule punktid ning leitakse miinimum ja maksimum nendes punktides arvutatud funktsiooni väärtustest. Tegelikult on võimalikud ekstreemumpunktid lõigu otspunktid ja tuletise nullpunktid. Vähemalt viimaste leidmine pole fikseeritud sammuga liikudes garanteeritud. Kuigi osa võtsid ka nooremate klasside õpilased, oli neil võimalik raamatuid kasutada ja õpetajalt konsultatsiooni küsida. Matemaatilise sisuga ülesande lahendamisel tuleb programmeerijal tihti ka midagi uut õppida. Kui olete ka ise programmi koostanud, siis testimisel soovitame veenduda, et programm annab tulemused ka juhtudel A=0 ja A=B=0.

2. ülesanne

Antud: 1-, 2-, 5-, 10-, 25- ja 100-krooniliste arvud kassas ja kaks maksmisele kuuluvat summat.

Leida: Kas need summad saab kassast täpselt välja maksta?

See ülesanne tekitas kõige rohkem probleeme. Tõenäoliselt peeti tsüklitega lahendamist liiga lihtsaks ja ka liiga aeglaseks. Keerulisemaid algoritme ei suudetud aga korrektselt kirja panna ja tihti puudus vist ka selge idee. Kui tõesti kõik rahatähtede arvud läbi proovida, tuleb programm tõepoolest suurema kassaseisu jaoks aeglane, eriti negatiivse vastuse puhul. Aga kui ilmselt mittevajalikud variandid välja jätta, väheneb läbivaatuste arv tunduvalt.

Allpool toodud programmis alustatakse kummagi summa kokkuseadmist suurematest kupüüridest ja vaadeldakse iga rahatähe korral nende arvu suurimast võimalikust alates. Peale maksimaalse antud summasse mahtuva arvu (SUMMA div VAARTUS) on vaja uurida ka 1 (mõnikord 2) võrra väiksemat kogust, sest

A. Iga rahatähe jaoks saab leida ülemise piirsumma, mida saab väiksematest ühikutest nii kokku panna, et sellest kombinatsioonist ühtegi osa ei saa vahetada antud rahatähega(tähtedega). Näiteks viieliste jaoks on piirsumma 8=2+2+2+2 ja igas ühe- ning kahekrooniste 9-kroonises või kallimas kombinatsioonis sisaldub mingi 5- või 10-kroonine osa, mida saab viielistega välja vahetada. Kümneliste jaoks on piirsumma 13, 25-liste jaoks 48 jne. Piirsumma ei ulatu kunagi rahatähe kahekordse väärtuseni. Fikseeritud ühe kogusumma jaoks maksmisvõimaluse leidmiseks pole seega vaja vaadelda väiksemat antud kupüüride arvu kui maksimaalne-1. Kui väiksemate rahadega makstakse juba kaks kupüüri väärtust, saab osa sellest kombinatsioonist välja vahetada.

B. Viimaste kahe 25-lise või 5-lise asemel tuleb mõnikord esimeses summas maksta väiksemate rahadega, et säilitada võimalus paaritu teise summa maksmiseks (näiteks summad 10 ja 5 rahade 5,5,2,2,2,2,2 korral).

3. ülesanne

Antud: Valge lipu ja kuninga ning musta kuninga asukohad (rohkem malendeid laual pole). Käigul on valge.

Leida:

1. Kas seis on võimalik?

2. Kas valge saab ühe käiguga teha mati?

Kolmas ülesanne koosnes kahest osast. Kõigepealt kontroll, kas seis on võimalik ja siis kontroll, kas valge saab ühe käiguga mati teha. Esimeses pooles tuli seejuures kontrollida, kas pole malendeid, mis asuksid ühel ruudul, kas kuningad pole kõrvuti ja kas must kuningas pole valge lipu tule all. Teises pooles tuli kontrollida, kas lipp saab teha mõne käigu nii, et must kuningas jääb tule alla ja kas seejärel mustal kuningal on võimalik tule alt ära käia või lippu lüüa. Kui ei ole, ongi matt.

Ülesandeid hinnati maksimaalselt vastavalt 10, 20 ja 30 punktiga. Lõppvoorule pääsemise piiriks kujunes 35-37 punkti (tegime paaripunktise soodustuse väljastpoolt Tallinna ja Tartut saadetud lahendustele). Kahjuks oli väga vähe korralikult vormistatud ja kergesti loetavaid programme.

Kommenteeris Rein Prank