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 1999 niet ouder zijn dan 20 jaar.
Als extra stimulans is er een prijs ter waarde van 1000 gulden voor een van de inzenders van een correcte oplossing van opgave 1. De oplossing van opgave 1 moet uiterlijk op 1 december 1998 binnen zijn (datum poststempel). De uitslag volgt uiterlijk 10 januari 1999. De oplossingen van alle opgaven moeten op 10 januari 1999 binnen zijn (datum poststempel). De uitslag volgt ongeveer een maand later. Deelnemers met een werkende inzending voor opgave 4 dingen mee naar de CvO-Windesheimprijs: Een bedrag van 500 gulden, 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. Daarop moeten de gemaakte programma's staan en de persoonlijke gegevens van de deelnemers. Over beide volgt hieronder nog meer. Op de diskettes moet de namen van alle deelnemers die er aan hebben meegewerkt staan vermeld. Op de envelop vermeld je eveneens namen, adressen en telefoonnummers van de deelnemers en de gebruikte programmeertaal of -talen. Ook inzenden via E-mail is mogelijk; zend alle gevraagde bestanden in een archieffile, bij voorkeur een self-extractor. Neem wanneer je niet binnen een week een ontvangstbevestiging hebt ontvangen altijd even contact op!
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 toegelaten tot de tweede ronde. De jury kan deze grens van 200 punten naar beneden bij 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.
Zet op de schijf een ASCII-file met de naam PERSGEG.1 (eventueel tot en met PERSGEG.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 vanaf PERSGEG.1, PERSGEG.2 enz. te worden vastgelegd:
| Op regel | komt te staan | voorbeeld |
| 1 | je achternaam | Waal |
| 2 | je voornaam | Anne |
| 3 | de eventuele voorvoegsels bij je naam | van de |
| 4 | je adres | Laan 2 |
| 5 | je postcode | 1074 HD |
| 6 | je woonplaats | Amsterdam |
| 7 | je (eventuele) telefoonnummer | 020 6123457 |
| 8 | je geboortedatum | 790321 (voor 21 maart 1979) |
| 9 | meisje of jongen | meisje |
| 10 | de naam van je school | Thorbecke Lyceum |
| 11 | de naam van je docent informatica of contactpersoon op je school | Wiel, drs. Henny van der |
| 12 | het adres van je school | Kerkstraat 15 |
| 13 | de postcode van je school | 1007 AD |
| 14 | de woonplaats van je school | Amsterdam |
| 15 | het telefoonnummer van je school | 020 4367842 |
Op het World Wide Web is een site met allerlei informatie
over de Nederlandse Informatica Olympiade. Het adres daarvan
is: http://olympiads.win.tue.nl/nio/
Hier staat ook een programma PAS.EXE;
daarmee kun je het spel van opgave 4 spelen.
Op hoeveel manieren kun je een stapel stenen leggen in de vorm van een trapezium? Een trapezium is een manier van neerleggen waarbij je met een rij stenen begint; iedere volgende rij is een vast aantal stenen langer. In totaal moet je alle stenen hebben gebruikt. Met een totaal van 15 stenen, waarbij elke volgende rij 1 langer wordt, kan dat op vier manieren; zie figuur 1.
Figuur 1. Vier trapezia met vijftien stenen; elke volgende rij wordt 1 langer
Schrijf een programma dat vraagt om een aantal stenen (maximaal 1000000000) en om het verschil in lengte tussen opvolgende rijen (maximaal 1000). Het programma geeft als uitvoer eerst een regel met daarop het aantal manieren waarop zo'n trapezium kan worden gemaakt; vervolgens de aantallen stenen van de eerste rij van elk van die trapezia, in oplopende grootte.
| Aantal stenen: | 15 |
| Verschil per rij: | 1 |
| 4 1 4 7 15 |
Als wekelijkse puzzel van de schoolkrant krijgen leerlingen een woord op waarbij ze van de letters van dat woord zo veel mogelijk bestaande woorden moeten maken. Ze leveren hun oplossing in op diskette. Eerst wordt de woordencontroleploeg van de schoolkrant er op losgelaten; daarna moet er nog worden gecontroleerd of alle woorden werkelijk uit de letters van het oorspronkelijke woord te maken zijn.
Schrijf een programma dat een bestand inleest en een juryrapport maakt. Het (al op spelling en bestaande woorden gecontroleerde) bestand is een ASCII-tekstbestand met op de eerste regel het oorspronkelijke woord; vervolgens zijn er de regels met op iedere regel een woord; de laatste regel bevat het woord STOP in hoofdletters. Alle andere woorden in het bestand bestaan uitsluitend uit kleine letters; spaties en leestekens zijn niet toegestaan. Ieder woord bestaat uit maximaal 20 tekens; het bestand bevat maximaal 2500 regels. In het juryrapport geeft het gevraagde programma de volgende informatie:
| APPEL.IN | Commentaar |
| appelboom appel boom pel bom mop pels mop moppen bel oom oma opa opoe tante pep pap mop opoe pop STOP |
het puzzelwoord woord 1 woord 2 woord 3 woord 4 woord 5 niet te maken 1 niet uniek 1 niet te maken 2 woord 6 woord 7 woord 8 woord 9 woord 10 niet te maken 3 woord 11 woord 12 niet uniek 2 niet uniek 3 woord 13 einde bestand |
| 19 13 3 3 |
Voor een experiment met het nieuwe referendum wil de overheid groepen gemeenten indelen in regio's. Een regio bestaat uit 1 of meer gemeenten, die zo verbonden zijn dat het mogelijk is om uit elk van de gemeenten uit de regio elk van de andere gemeenten te bereiken zonder dat je de regio hoeft te verlaten. Een regio heeft minstens 100000 inwoners. Alle gemeenten worden in precies 1 regio ingedeeld. Men streeft verder naar het vormen van zo veel mogelijk regio's. Daartoe zoekt men een geschikt computerprogramma.
Schrijf een programma dat een ASCII-tekstbestand GEBIED.IN inleest. Dat bestand heeft de volgende structuur:
De invoer is zodanig dat het altijd mogelijk is om 1 regio te maken van alle gemeenten in het bestand.
Het programma geeft als uitvoer een bestand REGIO.UIT. Dat bestand heeft de volgende structuur:
| GEBIED.IN | Commentaar |
| 6 126670 33443 80897 51758 25188 25272 8 1 3 1 6 2 3 2 4 2 6 3 4 3 6 4 5 |
er zijn 6 gemeenten in het bestand aantal inwoners van gemeente 1 aantal inwoners van gemeente 2 aantal inwoners van gemeente 3 aantal inwoners van gemeente 4 aantal inwoners van gemeente 5 aantal inwoners van gemeente 6 er zijn 8 onderlinge gemeentegrenzen gemeenten 1 en 3 grenzen aan elkaar gemeenten 1 en 6 grenzen aan elkaar gemeenten 2 en 3 grenzen aan elkaar gemeenten 2 en 4 grenzen aan elkaar gemeenten 2 en 6 grenzen aan elkaar gemeenten 3 en 4 grenzen aan elkaar gemeenten 3 en 6 grenzen aan elkaar gemeenten 4 en 5 grenzen aan elkaar |
| REGIO.UIT | commentaar |
| 3 1 2 3 2 2 3 | er zijn maximaal 3 regio's te vormen gemeente 1 ligt in de regio met gemeente 1 gemeente 2 ligt in de regio met gemeente 2 gemeente 3 ligt in de regio met gemeente 3 gemeente 4 ligt in de regio met gemeente 2 gemeente 5 ligt in de regio met gemeente 2 gemeente 6 ligt in de regio met gemeente 3 |
Figuur 2. Schets van het voorbeeldgebied
Het spel PAS wordt gespeeld door twee spelers, BRUIN en WIT, op een rechthoekig speelveld van 6 bij 5 vakjes (zie figuur 3). Beide spelers hebben 15 verschillende vierkante stenen; de hoeken van die stenen zijn rood, groen of blauw (zie tabel 1).
De spelers leggen, zolang ze nog niet gepast hebben, om beurten een steen op het bord; BRUIN begint. De kleuren van de hoeken van de gespeelde steen moeten overeenkomen met die op de hoeken van stenen op aangrenzende vakjes. Hoe beter een steen past, hoe meer paspunten je krijgt (zie figuur 4). Als je niet kunt zetten moet je passen; daarna mag je niet ook meer zetten. Als beide spelers hebben gepast is het spel afgelopen. De aantallen geplaatste stenen en de behaalde paspunten worden omgezet in wedstrijdpunten (zie tabel 2). Alle deelnemende programma's spelen twee onderlinge wedstrijden; de winnaar(s) van de hele competitie ontvangen de CvO-Windesheimprijs 1999.
Figuur 3. Het speelveld van PAS
Iedere steen heeft gekleurde hoekpunten; alle combinaties van rood, groen en blauw op de hoekpunten komt voor, maar met de klok mee gerekend heeft BRUIN alleen de volgorde rood-groen-blauw en WIT alleen de volgorde rood-blauw-groen. De vijftien stenen van een speler worden aangeduid met de letters A tot en met O. Een steen kan worden gedraaid en afhankelijk van de eventuele symmetrie op 1 of 4 manieren op het speelveld worden gelegd; deze draaiingen worden aangeduid met een cijfer 0, 1, 2 of 3 na de letter. In tabel 1 staan alle mogelijkheden genoemd; de kleuren worden aangeduid met R, G en B voor rood, groen en blauw.
Iedere gespeelde steen grenst aan maximaal 12 hoekpunten van andere stenen (zie figuur 4). Voor ieder van die hoekpunten waar al een steen ligt krijg je een paspunt; en omdat BRUIN telkens moet zetten in een situatie dat er nog minder stenen op het bord liggen, krijgt BRUIN aan het begin van het spel 10 extra paspunten.
Figuur 4. Mogelijke paspunten
De uitslag van een spel wordt omgezet in wedstrijdpunten; in totaal worden er 20 wedstrijdpunten verdeeld over beide spelers. Acht ervan worden bepaald door het aantal stenen dat je hebt kunnen plaatsen voor je moest passen in vergelijking met dat aantal van je tegenstander, volgens tabel 2. De andere twee gaan naar de speler met de meeste paspunten; bij gelijk eindigen worden die punten gedeeld.
Een ongeldige zet wordt door het wedstrijdprogramma beschouwd als een PAS; alleen de andere speler kan nu nog stenen plaatsen!
Tabel 1. Alle stenen in PAS
Tabel 2. Wedstrijdpunten
Schrijf een programma dat een spelverloop van een spelletje PAS inleest en vervolgens binnen 15 seconden een geldige zet doet; als je nog een zet kunt doen, mag je niet passen! Voor de Olympiade kun je 80 punten krijgen voor een werkend programma; de laatste 20 punten kunnen worden verdiend in het toernooi om de CvO-Windesheimprijs.
Een zet wordt weergegeven met behulp van vier tekens:
B3C1 betekent dat steen B, positie 3, wordt geplaatst op vakje C1.
Je programma krijgt als invoer een ASCII-tekstbestand SPEL.IN met de volgende structuur:
Voorbeeld van een invoerbestand:
| SPEL.IN | Commentaar |
| 3 A0D3 A0D2 F1D4 |
drie zetten gedaan BRUIN zet steen A, positie 0, op vakje D3 WIT zet steen A, positie 0, op vakje D2 BRUIN zet steen F, positie 1, op vakje D4 |
Je programma geeft als uitvoer een ASCII-tekstbestand ZET.UIT van 1 regel; deze regel bevat een geldige zet, of het woord 'PAS'.
Voorbeeld van uitvoer:
| ZET.UIT | Commentaar |
| C2C2 | WIT zet steen C, positie 2, op vakje C2 |
| Goede dialoog | 10 punten |
| Goede oplossing kleine gevallen | 60 punten |
| Snelle oplossing grote gevallen | 30 punten |
| Goede dialoog | 10 punten |
| Woorden in het bestand | 10 punten |
| Goedgekeurde woorden | 40 punten |
| Vaker voorkomen | 20 punten |
| Verkeerde woorden | 20 punten |
| Goede dialoog | 10 punten |
| Aantal regio's | 30 punten |
| Goede indeling | 50 punten |
| Bestand wegschrijven | 10 punten |
| Goede bestanden | 10 punten |
| Geldige zet | 50 punten |
| Passen als het niet anders kan | 20 punten |
| Plaats CvO-Windesheimtoernooi | 20 punten |