Voorwaarden en aanwijzingen

De Nederlandse Informatica Olympiade is een wedstrijd voor leerlingen uit het voortgezet
onderwijs. Aan de eerste en tweede ronde mag iedereen meedoen die dit schooljaar op
een vbo, mavo, havo of vwo zit. Aan de extra scholing en de derde ronde kunnen
leerlingen meedoen die op 1 juli 1997 niet ouder zijn dan 19 jaar en in het leerjaar
1997/1998 nog op een vbo, mavo, havo of vwo zitten.

Het inzenden van je oplossingen

Als extra stimulans is er een prijs ter waarde van ź 1000,- voor ‚‚n van de inzenders van
een correcte oplossing van opgave 1. De oplossing van opgave 1 moet op 1 december
1996 binnen zijn (datum poststempel). De uitslag volgt voor 5 januari 1997.
De oplossingen van alle opgaven moeten op 15 januari 1997 binnen zijn (datum poststem-
pel). De uitslag volgt ongeveer een maand later.
Deelnemers met een werkende inzending voor opgave 4B dingen mee naar de CvO-
Windesheimprijs: Een bedrag van ź 500,-, beschikbaar gesteld voor de student of docent
die het toernooi bij deze opgave weet te winnen.
Zend je oplossing in op een tweetal identieke diskettes. Op die diskettes moeten de
gemaakte programma's staan en de persoonlijke gegevens van de deelnemers. Over
beide volgt hieronder nog meer. Op de diskettes moet de naam van alle deelnemers die er
aan hebben meegewerkt staan vermeld. Op de envelop vermeld je eveneens naam, adres
en telefoonnummer van de deelnemers en de gebruikte programmeertaal of -talen.

De programma's:

-      Gebruik een hogere programmeertaal op een MS-DOS-computer. 
-      Gebruik als programmanamen NIO1, NIO2, NIO3, NIO4A en NIO4B (eventueel met
       een achtervoegsel dat aangeeft welke programmeertaal is gebruikt). 
-      Lever de programmatekst en ook een gecompileerde versie (een .EXE-bestand). 
-      Een beschrijving van de opzet van het programma kan als commentaar in de
       programmatekst worden opgenomen.
-      Gebruik het toetsenbord voor het geven van invoer (en in ‚‚n geval een bestand
       op diskette); uitvoer gaat altijd naar het beeldscherm. 
-      In de voorbeelden bij de opgaven staat aangegeven welke dialoog er van je
       programma wordt verwacht.
-      Geef duidelijk aan of je programma bijzondere eisen stelt aan de hardware
       (bijvoorbeeld een speciale grafische kaart), bijvoorbeeld in de eerste tekst die het
       programma presenteert of anders in het commentaar aan het begin van de
       programmatekst. Overigens is het bij geen van de opgaven noodzakelijk gebruik te
       maken van een grafische mode!
-      Heb je, bij het maken van een programma, een eigen interpretatie moeten geven
       van de opgave, meld dat dan in de tekst die het programma op het beeldscherm
       presenteert. De jury kan daar dan rekening mee houden.
-      Voor ieder programma geldt een tijdslimiet van 15 seconden op een PC met een
       Pentium 75 processor. Oplossingen die te veel tijd vergen krijgen geen punten.

Waardering en vervolg

Voor iedere opgave kun je maximaal 100 punten verdienen. Na de opgaven staat een
puntenverdeling aangegeven. Heb je minstens 200 van de 400 mogelijke punten gehaald
dan krijg je het Certificaat Nederlandse Informatica Olympiade uitgereikt en word je toege-
laten tot de tweede ronde. De jury kan deze grens van 200 punten naar beneden bij te
stellen; daarom is het verstandig om ook als je denkt niet aan de 200 punten te komen
toch in te zenden.
Tijdens de tweede ronde zijn alleen de volgende programmeertalen toegestaan: Turbo
C++ versie 3.0, Turbo Pascal 7.0 en Quick BASIC 4.5.

Persoonlijke gegevens.

Zet op de schijf een ASCII-file met de naam PERSGEG.1 (eventueel tot en met PERS-
GEG.999) met daarin de persoonlijke gegevens van de deelnemers.
Houd je daarbij strikt aan de volgende beschrijving.

Voor elk groepslid dient in een aparte file oplopend van PERSGEG.1, 
PERSGEG.2 enz. te worden vastgelegd:

op regel 1    je achternaam (bijvoorbeeld: Waal)
op regel 2    je voornaam (bijvoorbeeld: Anne)
op regel 3    de eventuele voorvoegsels bij je naam (bijvoorbeeld: van de)
op regel 4    je adres (bijvoorbeeld: Laan 2)
op regel 5    je postcode (bijvoorbeeld: 1074 HD)
op regel 6    je woonplaats (bijvoorbeeld: Amsterdam)
op regel 7    je (eventuele) telefoonnummer (bijvoorbeeld: 020 6123457)
op regel 8    je geboortedatum (bijvoorbeeld: 790321 (voor 21 maart 1979))
op regel 9    meisje of jongen (bijvoorbeeld: meisje)
op regel 10   de naam van je school (bijvoorbeeld: Thorbecke Lyceum)
op regel 11   de naam van je docent informatica of contactpersoon op je school (bijvoorbeeld: Wiel, drs.
              Henny van der)
op regel 12   het adres van je school (bijvoorbeeld: Kerkstraat 15)
op regel 13   de postcode van je school (bijvoorbeeld: 1007 AD)
op regel 14   de woonplaats van je school (bijvoorbeeld: Amsterdam)
op regel 15   het telefoonnummer van je school (bijvoorbeeld: 020 4367842)

Vragen en inlichtingen.

Op het bulletinboard SLO-Lijn is een apart gebied beschikbaar voor deelnemers aan de
Nederlandse Informatica Olympiade. Hier zijn bijvoorbeeld uitwerkingen te vinden van
opgaven uit vorige jaren. Ook staat er een versie van het spel Hexxagon uit opgave 4.
Je kunt hier ook vragen deponeren over de opgaven; je krijgt dan binnen een week een
reactie.

Het telefoonnummer van SLO-Lijn is 053 4341634. De instellingen van je modem moeten
zijn: Geen pariteit, 8 databits en 1 stopbit. 

Op het World Wide Web is een site met allerlei informatie over de Nederlandse Informatica
Olympiade. Het adres daarvan is: http://www.win.tue.nl/win/nio/

Je stuurt je oplossingen naar:

Nederlandse Informatica Olympiade
p/a Christelijke Hogeschool Windesheim
Faculteit Onderwijs
t.a.v. de heer Willem van der Vegt
Postbus 10090
8000 GB Zwolle
Tel. 038 4699534
E-mail: W.van.der.Vegt@chw.nl

Opgave 1. Spijkercijfers

De Babyloni‰rs gebruikten twee symbolen om getallen mee te schrijven: De "spijker" en de
"winkelhaak". De spijker geven we hier aan met een I, de winkelhaak met het teken <.
De Babyloni‰rs hebben een zestigtallig stelsel. Daarbij kan een I staan voor 1 keer 1, of
voor 1 keer 60, of voor 1 keer 3600, of voor 1 keer 1/60, of voor 1 keer 1/3600, en
zo voorts. Een < is 10 keer zo veel waard, dus 10 keer 1, of 10 keer 60, enzovoorts. Het
getal 13 maken de Babyloni‰rs door te schrijven <III. 
Ten opzichte van ons getallensysteem zijn er drie problemen die het moeilijk maken om
een getal te lezen. Allereerst is er geen teken voor de nul; zo kan <I staan voor 11, maar
ook voor 10 keer 60 plus 1 keer 1, of voor 11 keer 60, enz. In de tweede plaats is er geen
teken voor wat wij als de komma hebben, een scheiding tussen hele en gebroken getallen;
zo kan <I ook staan voor  11/60 of voor 10+1/60. Tenslotte is het niet altijd mogelijk om
een serie symbolen eenduidig op te vatten omdat II zowel 2 als 1 keer 60 plus 1 keer 1
kan betekenen. De in een getal gebruikte symbolen staan wel in afnemende volgorde: <II
betekent bijvoorbeeld 10x60+2x1 of 10x1+2x1, maar nooit 10x1+2x60.
Om aan alle mogelijke verwarring het hoofd te kunnen bieden zoeken we een programma
dat mogelijke interpretaties van getallen in spijkerschrift kan controleren. Om ook breuken
te kunnen invoeren splitsen we getallen in twee gedeelten, eerst het gehele deel, vervol-
gens het gebroken gedeelte, uitgedrukt in zesendertighondersten. Met 3 400 als invoer
wordt 3 + 400/3600 bedoeld.

Schrijf een programma dat:

-      Eerst een regel inleest met een getal in spijkerschrift (waarbij een < gebruikt wordt
       voor een winkelhaak en een I voor een spijker). Het getal bestaat uit niet meer dan
       15 symbolen.
-      Vervolgens telkens een regel inleest met twee getallen, die respectievelijk staan
       voor de eenheden (niet groter dan 10 tot de 7-de) en de zesendertighondersten van een
       mogelijke betekenis van het spijkerschriftgetal (zie ook het voorbeeld) en daarna
       aangeeft of deze interpretatie wel of niet klopt.
-      Stopt als een regel "0 0" wordt ingevoerd.

Voorbeeld:

Geef een spijkergetal:             <II<<I
Mogelijke betekenis:               741 0         
                                   OK
Mogelijke betekenis:               602 611
                                   OK
Mogelijke betekenis:               10 1271
                                   FOUT
Mogelijke betekenis:               39660 1201
                                   OK
Mogelijke betekenis:               0 0
Einde programma.

Opgave 2. Dit lijkt te rijmen

Als voorbereiding op de Sinterklaastijd wil Jos al vast idee‰n opdoen voor passende
rijmwoorden. Daarom zoekt hij een computerprogramma dat een tekst kan inlezen;
vervolgens moet het programma aangeven welke woorden in die tekst "schijnrijmen". Twee
woorden schijnrijmen als ze eindigen met dezelfde serie van minstens drie letters (waar
minstens ‚‚n klinker bij hoort te zitten), en die serie bij beiden nog door andere letter(s)
wordt voorafgegaan. Een woord eindigt voor een spatie of een leesteken, of op het eind
van een regel of aan het eind van een bestand. De y geldt net als de a,e,i,o en u als
klinker.

Voorbeelden:

schater       kater         schijnrijmen
schat         kat           schijnrijmen niet (geen drie letters in de serie!)
wonder        onder         schijnrijmen niet (onder is een heel woord!)
angst         engst         schijnrijmen niet (geen klinker in gemeenschappelijke serie!)
wonder        ander         schijnrijmen
beleid        tijd          schijnrijmen niet

Aan de laatste twee voorbeelden kun je zien dat rijmen en schijnrijmen heel verschillende
dingen zijn!

Schrijf een programma dat:

-      Vraagt naar de naam van een tekstbestand (dat is een ASCII-tekstbestand dat
       bestaat uit maximaal 10 regels, ieder van maximaal 80 tekens; uitsluitend kleine
       letters, spaties en leestekens worden gebruikt).
-      De inhoud van dat tekstbestand op het scherm afbeeldt.
-      Een lijst geeft van hoogstens 10 groepen woorden in de tekst die onderling twee
       aan twee schijnrijmen. Als er niet meer dan 10 van die groepen te vinden zijn
       moeten ze allemaal worden afgebeeld. Een woord komt maar ‚‚n keer in zo'n
       groep voor; het kan dus zijn dat er binnen een groep deelgroepjes zijn van
       woorden die nog meer laatste letters gemeenschappelijk hebben.
-      Er voor zorgt dat de gebruiker, wanneer de lijst te groot is om in ‚‚n keer op het
       scherm te passen, af en toe op een toets moet drukken om verder te gaan.

Voorbeeld:

Naam invoerbestand: TEST.IN

groningen leeuwarden assen zwolle arnhem lelystad
utrecht haarlem den haag middelburg den bosch maastricht
reitdiep sneekermeer hoofdvaart vecht rijn ketelmeer
lek zaan merwede schelde dieze maas
koningen friezen motoren twente veluwe polder
vallei beschuit haven dijken varkens heuvels
toren beerenburg heide textiel fruit schepen
universiteit hoofdstad residentie strand fabrieken bier
goed slecht matig okay beschuit terecht ermee

Groepen die schijnrijmen:

groep 1: "oningen"          groningen 
                            koningen
groep 2: "stad"             lelystad 
                            hoofdstad
groep 3: "echt"             utrecht 
                            vecht 
                            slecht 
                            terecht
groep 4: "burg"             middelburg 
                            beerenburg
groep 5: "meer"             sneekermeer 
                            ketelmeer
groep 6: "uit"              beschuit 
                            fruit
groep 7: "ken"              dijken 
                            fabrieken

Merk op dat in groep 3, de woorden die eindigen op "echt", de woorden utrecht en terecht
nog meer letters gemeenschappelijk hebben. Omdat deze woorden al in een groep
voorkomen is er geen aparte groep meer aan ze gewijd.
Het woord beschuit, dat twee keer in de tekst voorkomt, wordt toch maar ‚‚n keer in de
lijst opgenomen.

Opgave 3. De grachten van Concentri‰

In de stadskern van Concentri‰ liggen zes cirkelvormige grachten met een gemeenschap-
pelijk middelpunt. Deze grachten zijn verbonden met acht radiale verbindingskanaaltjes.
Zie voor een plattegrond figuur 1. De grachten zijn genummerd van 1 tot en met 6 (van
binnen naar buiten), elke gracht bestaat uit 8 grachtdelen, opvolgend aangegeven met het
nummer van de gracht en een letter van A tot en met H, dus bijvoorbeeld 3A, 2C, 6H. 
In het hart van deze grachten, het gemeenschappelijke middelpunt, ligt het botenhuis van
de gemeentelijke groendienst. Van daaruit vertrekt iedere ochtend een schoonmaakboot,
die de oevers van enkele grachtdelen moet schoonmaken. Na afloop van het schoonmaak-
werk keert deze boot terug in het botenhuis. Uiteraard is een programma om voor dat
schoonmaken een planning te maken erg welkom.

Wat gegevens:

Een tocht over een verbindingskanaal van gracht tot gracht kost 4 minuten.
Een tocht over een gracht met volgnummer n van een verbindingskanaal naar een
volgende verbindingskanaal kost 3n minuten.
Het schoonmaken van een grachtdeel van gracht n kost 11n minuten.
Keren op een kruispunt mag, dit kost geen tijd.

Schrijf een programma dat:

-      Een getal inleest dat aangeeft hoeveel grachtdelen er moeten worden schoonge-
       maakt (maximaal 10).
-      De schoon te maken grachtdelen inleest.
-      Een lijst geeft met een route van de schoonmaakboot waarbij de totale reis- en
       werktijd onderweg zo klein mogelijk is. Alleen de grachtdelen die moeten worden
       aangedaan worden aangegeven; voor de route twee opvolgende grachtdelen in de
       route wordt zo mogelijk het verbindingskanaaltje waarop beide grachtdelen
       uitkomen gebruikt, als dat niet kan loopt de route via het centrale botenhuis.
-      De totale gebruikte tijd (reistijd en werktijd) in minuten aangeeft.

Voorbeeld:

Hoeveel grachtdelen schoonmaken:                        5      
Geef de 5 schoon te maken grachtdelen:                  3D
                                                        3F
                                                        6E
                                                        3E
                                                        5A
Planning:            5A 3B 3C 3D 3E 3F 3F 6E
Tijd:                311 minuten

Zie voor de aangegeven route ook figuur 1 hiernaast.

Opgave 4. Hexxagon

Het spel Hexxagon wordt gespeeld op een zeshoekig speelveld. Het veld is opgebouwd uit
zeshoekige vakjes, die dus elk grenzen aan maximaal zes andere vakjes, de buurvakjes.
Langs elke zijde van het veld liggen 5 vakjes; in totaal heb je zo 61 vakjes. Elke keer dat
Hexxagon wordt gespeeld doen 3 van deze 61 vakjes niet mee; deze worden aangegeven
met een X. Gedurende dat spelletje blijven dit dezelfde 3 vakjes; een volgend spel kunnen
dat weer andere zijn.
Het spel wordt gespeeld door twee spelers; de ‚‚n heeft Rood, de ander Wit. Aan het
begin van het spel hebben beide spelers een steen van hun kleur op drie vakjes. Doel van
het spel is aan het einde ervan zoveel mogelijk vakjes in het bezit te hebben. De spelers
doen om beurten een zet; Rood begint. Er zijn twee mogelijke zetten: Bijplaatsen en
Springen.
Bij Bijplaatsen zet een speler een steen van zijn kleur op een leeg vakje naast een eigen
steen. Bij Springen wordt met een steen van de eigen kleur over een willekeurig buurvakje
heen gesprongen naar een leeg vakje (zie figuur 2). In beide gevallen worden alle
buurvakjes van het nu gevulde vakje met een steen van de tegenstander nu gevuld met
een steen van de kleur van de speler.
Als een speler niet kan zetten moet hij de beurt overslaan; als beide spelers niet meer
kunnen zetten is het spel afgelopen. In een competitie (zie opdracht B) wordt het aantal
bezette vakjes van de speler zelf en de tegenstander bijgehouden als een soort doelsaldo.

Figuur 2. Mogelijke zetten in Hexxagon; maar een deel van het speelveld is afgebeeld.

W: Witte steen.
B: Vakjes waar een witte steen kan worden bijgeplaatst (als ze leeg zijn).
S: Vakjes waar met de witte steen naar toe kan worden gesprongen (als ze leeg zijn).

        S   S   S
      S   B   B   S
    S   B   W   B   S
      S   B   B   S
        S   S   S

Figuur 3. Een stelling in HEXXAGON:

Wit aan zet

          R   R   W   R   R
        R   W   W   W   W   R
      R   W   W   .   .   W   R
    R   W   .   X   .   .   W   W
  R   R   R   .   .   X   .   .   W
    R   R   R   X   .   .   W   W
      .   .   W   W   W   R   R
        W   R   W   R   W   R
          W   .   .   R   R

Figuur 4. Mogelijke zetten in de stelling van figuur 3.
Op de lege vakjes staat aangegeven op hoeveel manieren daar kan worden bijgeplaatst
(totaal 28 keer).

          R   R   W   R   R
        R   W   W   W   W   R
      R   W   W   3   3   W   R
    R   W   3   X   0   2   W   W
  R   R   R   0   0   X   2   5   W
    R   R   R   X   2   2   W   W
      1   2   W   W   W   R   R
        W   R   W   R   W   R
          W   2   1   R   R

Op de lege vakjes staat aangegeven op hoeveel manieren daar naar toe kan worden
gesprongen (totaal 58 keer).

          R   R   W   R   R
        R   W   W   W   W   R
      R   W   W   5   4   W   R
    R   W   2   X   6   4   W   W
  R   R   R   5   4   X   5   1   W
    R   R   R   X   4   4   W   W
      2   3   W   W   W   R   R
        W   R   W   R   W   R
          W   3   5   R   R

Opdracht A:

Schrijf een programma dat inleest wie aan zet is (R of W) en vervolgens een stelling
ingevoerd krijgt (zie voorbeeld hieronder). Als uitvoer geeft het programma het aantal
verschillende zetten dat door de speler die aan zet is gedaan kan worden; eerst een regel
met het aantal manieren waarop een steen kan worden bijgeplaatst, vervolgens een regel
met het aantal manieren waarop kan worden gesprongen. (Bijplaatsen op en springen naar
een leeg vakje telt vanuit alle buurvakjes een keer mee!)

Voorbeeld:

Invoer:       W
              RRWRR
              RWWWWR
              RWW..WR
              RW.X..WW
              RRR..X..W
              RRRX..WW
              ..WWWRR
              WRWRWR
              W..RR

Uitvoer:      28
              58

Opdracht B:

Schrijf een programma dat net als bij opdracht A gegevens over een stelling inleest.
Ditmaal kiest het programma ‚‚n van de mogelijke zetten; het speelbord wordt aangepast
en als uitvoer geeft het programma eerst een regel met daarop de letter van degene die
nu aan zet is (R of W), vervolgens de stelling na de gedane zet. Als er geen zet gedaan
kan worden, wordt de onveranderde stelling uitgevoerd.

Voorbeeld:

Invoer:       R
              R...W         
              WW..RR
              RRR..RW
              WW.X...W
              R....X..R
              ...X....
              .......
              ......
              R...W

Uitvoer:      W
              RR..W
              WR..RR
              RRR..RW
              WW.X...W
              R....X..R
              ...X....
              .......
              ......
              R...W

Het toernooi om de CvO-Windesheimprijs.

Goed werkende programma's nemen deel aan het toernooi om de CvO-Windesheimprijs.
Alle deelnemende programma's spelen twee wedstrijden tegen elk van de andere
deelnemers, een keer met Rood en een keer met Wit. Winst levert 2 wedstrijdpunten op,
gelijkspel 1, verlies 0. Naast de wedstrijdpunten worden de behaalde stenen voor en tegen
per wedstrijd vastgelegd; bij gelijk eindigen in wedstrijdpunten wint de deelnemer met het
beste steensaldo. Als het dan nog gelijk is wordt de prijs tussen de beste deelnemers
verdeeld.
Een wedstrijd wordt gespeeld door eerst het programma dat met Rood speelt een
beginstelling als invoer aan te bieden. De uitvoer van dit programma wordt door het
programma dat Wit heeft als invoer gebruikt, en zo wordt de stelling tussen beide
programma's heen en weer geschoven tot het spel is afgelopen. Iedere keer dat je
programma wordt aangeroepen krijgt het maximaal 15 seconden de tijd om uitvoer te
produceren!

Een technische randvoorwaarde.

Om deelnemende programma's aan het toernooi om de CvO-Windesheimprijs op een
goede manier tegen elkaar te laten spelen is het van belang dat bij in- en uitvoer stan-
daard input en output worden gebruikt! Dat betekent in Pascal geen unit crt gebruiken en
in C geen conio! Je programma zal namelijk met behulp van IO-redirection invoer uit een
bestand krijgen en uitvoer naar een bestand sturen. De MSDOS-opdracht om dat te doen
is iets als "NIO4B < IN.TST > UIT.TST", waarbij NIO4B de naam van je programma is,
IN.TST een bestand met de hierboven gespecificeerde invoer en UIT.TST een bestand
met de uitvoer in hetzelfde formaat.Punten per opgave:

Opgave 1.     Goede dialoog:                     30 punten
              Correcte antwoorden:               70 punten

Opgave 2.     Goede dialoog:                     10 punten
              Goede weergave invoertekst:        20 punten
              Juiste groepen gevonden:           50 punten
              Valkuilen vermeden:                20 punten

Opgave 3.     Goede dialoog:                     20 punten
              Planning zo snel mogelijk:         40 punten
              Lastige gevallen binnen de tijd:   20 punten
              Correcte reistijd bij route:       20 punten

Opgave 4      Goede dialoog 4A:                  10 punten
              Goede aantal mogelijke zetten:     40 punten
              Goede dialoog 4B:                  10 punten
              Correcte zetten doen:              20 punten
              Klassering in toernooi:            20 punten

Totaal                                          400 punten