24. aprill 1994. a. Rahvusvahelise informaatikaolümpiaadi katsevõistluse ülesanded

24. aprill 1994. a.

IOI kandidaatide katsevõistluse ülesanded

Koostada programmid järgmiste ülesannete lahendamiseks. Programmide tekstid paigutada Teile antud kettale failidesse, mille nimi on saadud ülesande numbri lisamisel Teie perekonnanime lõppu, näiteks TAMM1.PAS, TAMM2.PAS, TAMM3.PAS.

Iga programm peab alustama tööd autori ja ülesande teatamisega (viimaseks piisab ühest lausest).
Kui andmed sisestatakse failist, siis küsitakse kasutajalt faili nimi.
Programmid ei pea kontrollima sisendandmete vastavust ülesande tekstis olevatele tingimustele. Testimisel kasutab komisjon ainult korrektseid algandmeid.
Programm peab reageerima adekvaatselt ja andma välja mõistliku teate (mitte katkestama tööd või jätma vastust andmata) ka selliste andmete korral, millele reageerimine ei ole ülesande tekstis kirjeldatud, aga mis vastavad ülesandes antud sisendtingimustele.

Ülesannete tekstides mainitud failid on olemas ka Teile antud ketastel. Ootamatuste vältimiseks soovitame salvestada programmi tekst perioodiliselt a: -kettale.

1. ülesanne ( 20 p ). NELI LÕIKU

On teada, et lõigud AB, BC, CD ja DA moodustavad mittetühja sisemusega kumera nelinurga või kolmnurga.

Tekstifailis on igal real üks väide mingite kahe eeltoodud lõigu võrdsuse või paralleelsuse (kollineaarsuse) kohta (kuni 10 rida). Kui võimalik, siis järeldada, et kujund on trapets, rööpkülik, ristkülik, romb, ruut või kolmnurk.

Näiteid:
  Fail T1.1
AB=BC
AB=AD
BC=DC
romb
  Fail T1.2
AB∥BC
kolmnurk
  Fail T1.3
AB=BC
ei järeldu ükski väidetest

2. ülesanne ( 20 p. ) PROGRAMMI ANALÜÜS

Tööpinki juhtivas arvutis kasutatakse programmeerimiseks keelt, milles kirjutatud programm koosneb ühest või mitmest protseduuri kirjeldusest ja põhiprogrammiks loetakse esimest protseduuri, mille nimega saab ka programmi poole pöörduda.

Iga protseduuri kirjeldus algab märgiga '#', millele järgneb vahetult protseduuri nimi. Sellele järgneb märk '$', mis tähistab protseduuri sisu algust, siis järgneb protseduuri sisu, mis koosneda suurte tähtedega kirjutatud väljakutsutavate protseduuride nimedest ning numbritest, mis on käsud vastavale tööpingile. Protseduuri sisu kirjeldus lõpeb jällegi märgiga '$'.

Protseduuri kirjelduse näiteks on
#ALGUS$216BKSU42$ , kus 'ALGUS' on protseduuri nimi.

Keele süntaksi kohaselt

1. ei tohi ükski protseduuri nimi sisaldada teise protseduuri nime;

2. tühikud ja reavahetused ei oma programmis mingisugust tähendust.

Seega võib programmi kirjutada ka järgmisel viisil:

#A$BCDE$ #B$26$# E $ D 1 B $
#C$12B$#
D
$997$

Selleks, et tööpingil programmi täites ei juhtuks ootamatusi, s.t. tööpingi töö katkemist või lõpmatusse tsüklisse jäämist, on eelnevalt tarvis arvuti abil kontrollida, et:

1. iga protseduur kutsub välja ainult kirjeldatud protseduure.

2. programmis ei oleks tsüklilisi pöördumisi.

Koostada programm, mis loeb sisendfailist tööpingiprogrammi ja kontrollib nõudeid 1) ja 2).

Näited:
Fail T2.1
#A$BCDE$
#B$26$
#E$D1B$
#C$12B$
#D$997$
Programm korrektne.
  Fail T2.2
#A$C$
#B$26D$
#C$12B$
#D$9A97$
Eksisteerib tsükkel: A - C - B - D - A
  Fail T2.3
#A$CGF$
#B$26D$
#C$12B$
#D$997$
Leidub kirjeldamata protseduure. Reas 1: 'GF'

3. ülesanne ( 20 p. ). KASTID

N kasti kohta (N≤50) on antud nende igaühe kolm mõõdet. Ühte kasti saab transpordiks paigutada teise sisse, kui teda saab keerata mingile tahule nii, et kõik kolm mõõdet on väiksemad välimise kasti vastavatest mõõdetest (kaldu keerata ega pöörata ei tohi).

Antud: kahe kasti numbrid. Mitu kasti esialgsetest saab paigutada üksteise sisse nii, et üks nendest kahest kastist oleks välimine ja teine sisemine?

Sisendfailis on esimesel real N, teisel real kahe kasti numbrid, järgmistel N real kastide mõõtmed (täisarvud). Vastuses anda kokku pakitavate kastide arv ja nende numbrid koos mõõtmetega, alustades välimisest kastist.

Näide: Fail T3.1
4
1 2
8 10 10
5 4 3
5 7 9
9 6 6
    Vastus:
3 kasti
1: 8 10 10
3: 5 7 9
2: 5 4 3