1999-2000

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 v(m)bo, mavo, havo of vwo zit. Aan de extra scholing en de derde ronde kunnen leerlingen meedoen die op 1 juli 2000 niet ouder zijn dan 20 jaar.

Het inzenden van je oplossingen

Als extra stimulans is er een prijs ter waarde van 1000 gulden en 5 troostprijzen van 200 gulden voor inzenders van een correcte oplossing van opgave 1. De oplossing van opgave 1 moet uiterlijk op 1 december 1999 binnen zijn (datum poststempel). De uitslag volgt uiterlijk 10 januari 2000. De oplossingen van alle opgaven moeten op 10 januari 2000 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 leerling 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 moeten 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!

De programma's:

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 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.

Persoonlijke gegevens

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

Vragen en inlichtingen

Op het World Wide Web is een site met allerlei informatie over de Nederlandse Informatica Olympiade. Hier staat ooke en programma waarmee je het spel van opgave 4 kunt spelen. Het adres is: http://olympiads.win.tue.nl/nio/

Je stuurt je oplossingen naar:

Opgave 1. Wachttijdindicator.

In verschillende gemeentes zijn bij fietsverkeerslichten zogenaamde wachttijdindicatoren geplaatst. Dat zijn lichten naast het gewone verkeerslicht. Ze worden geactiveerd als zich een fietser meldt (bijvoorbeeld door op een knopje te drukken). Er gaat een verzameling lampjes branden die langzamerhand uitgaan; als alle lampjes uit zijn springt het verkeerslicht op groen.

 

 

Nu zul je de ene keer maar kort hoeven te wachten, maar een andere keer veel langer. Toch begint de indicator met alle lampjes aan. Het is de bedoeling dat de lampjes in gelijkmatig tempo uitgaan. Jouw programma moet daar een zo goed mogelijke manier voor vinden.

Schrijf een programma NIO1 dat als invoer krijgt van het toetsenbord een aantal lampjes n (niet meer dan 60) en een wachttijd t (in seconden, maximaal 120). t is in deze opgave altijd groter dan n. Uitvoer naar het beeldscherm is een lijstje van n regels; op elke regel staat een geheel getal. Dit getal geeft per lampje aan na hoeveel seconden het betreffende lampje wordt uitgeschakeld. Deze getallen zijn zo gekozen, dat de verhouding tussen het aantal lampjes dat al uit is en het aantal seconden dat is verstreken de verhouding van n en t zo goed mogelijk benadert; daarbij moet op de gebruikelijke manier worden afgerond, dus 7˝ wordt 8, maar 7,49 wordt 7.

Voorbeeld:

Invoer:

Lampjes:

5

 

Wachttijd:

13

Uitvoer:

3

 

 

2

 

 

3

2

3

 

 

 

Opgave 2. Woordgolf.

Bij woordgolf gaat het erom van een gegeven beginwoord naar een gegeven eindwoord te komen door een keten te maken van toegestane woorden die telkens maar één letter van elkaar verschillen.

Zo kom je bijvoorbeeld van WENS naar DAAD:

WENS

MENS

MANS

DANS

DAAS

DAAD

 

Schrijf een programma NIO2 dat als invoer krijgt een bestand GOLF.IN. De eerste regel bevat het beginwoord, de tweede regel het eindwoord. Op de derde regel staat een getal w dat aangeeft hoeveel toegestane woorden in het bestand voorkomen (meer dan 5, minder dan 1000). Daarna komen w regels met telkens één toegestaan woord. Het begin- en eindwoord hoeven daar niet meer bij te zitten! Alle woorden in het bestand bestaan uit hoofdletters; ze hebben allemaal evenveel letters, nooit meer dan 10.

Je programma schrijft de uitvoer naar een bestand GOLF.UIT.

Als het gelukt is een keten te maken schrijf je op de eerste regel het getal 0, en op de volgende regels de woorden van de golf, inclusief begin- en eindwoord. Als het niet kan zoek je een keten die bij het beginwoord begint en eindigt bij een woord dat zo wenig mogelijk letters van het gevraagde eindwoord verschilt. Het aantal letters dat je laatste woord van het eindwoord verschilt zet je op de eerste regel van het bestand; daarna geef je alle woorden van de keten die je gevonden hebt, gevolgd door een regel met het woord "stop" (in kleine letters).

Je kunt een deel van de punten van deze opgave verdienen door een golf te vinden die uit zo weinig mogelijk woorden bestaat!

Voorbeeld:

Invoer:

WENS

 

DAAD

 

10

 

AUTO

 

DAAS

 

DANS

 

EEND

 

EGEL

 

EVER

 

MANS

 

MENS

 

OLIE

 

ZOUT

 

 

Uitvoer:

0

 

WENS

 

MENS

 

MANS

 

DANS

 

DAAS

 

DAAD

 

Voorbeeld 2:

Invoer:

MENS

 

DIER

 

6

 

MEES

 

VINK

 

PIET

 

PEES

 

PIER

 

MEER

 

 

Uitvoer:

2

 

MENS

 

MEES

 

MEER

stop

 

Opgave 3. Maak een rechthoek.

 

Een tegelzetter heeft meestal wel een aantal overgebleven tegels liggen. Hij wil er graag een zo groot mogelijke rechthoek van maken. Omdat aantallen en vormen tegels kunnen verschillen, zoekt hij een programma waarmee hij die aantallen en vormen kan invoeren; het programma geeft dan een ontwerp voor een zo groot mogelijke rechthoek (dat is een rechthoek met een zo groot mogelijke oppervlakte). Hierbij mag je stenen wel roteren, maar niet spiegelen (de achterkant is meestal niet te gebruiken).

Hij heeft tegels waarvan de vorm met een hoofdletter wordt aangegeven. Alle hoeken van de tegels zijn 90 graden, alle lengtes van zijden zijn een geheel aantal decimeters.

In deze figuur zie je de negen vormen, aangeduid met H,L,T,I,O,U,J,P en Y. De kleuren worden alleen gebruikt om de verschillende vierkanten waaruit de tegels zijn opgebouwd duidelijk aan te geven.

Schrijf een programma NIO3 waarmee je de aantallen tegels kunt invoeren uit een bestand TEGELS.IN. Uitvoer is een bestand TEGELS.UIT.

 

Het invoerbestand begint met een regel waarop een getal n staat. Dat wil zeggen dat er n verschillende soorten tegels zijn, minstens 1, niet meer dan 6.

Vervolgens komen er n regels met elk eerst een hoofdletter (die aanduidt om welke vorm tegel het gaat), vervolgens een spatie en dan een getal dat aangeeft hoeveel tegels van deze vorm er zijn. In totaal zijn er maximaal 15 tegels aanwezig.

Het uitvoerbestand begint met getallen m en k, die aangeven wat de lengte en breedte van de gemaakte rechthoek zijn. Vervolgens komen er n regels met telkens een hoofdletter (die aanduid om welke vorm tegel het gaat), vervolgens een spatie en dan een getal dat aangeeft hoeveel tegels van deze vorm in de rechthoek gebruikt kunnen worden. Daarna komen m regels met daarop telkens k letters. Deze regels geven een soort bouwschets van de rechthoek; iedere letter duidt aan dat op de betreffende positie een deel van een tegel van het aangegeven type ligt.

Tegels mogen elkaar niet overlappen en niet uitsteken buiten de rechthoek. Ook mag je geen lege plekken overhouden binnen de rechthoek.

 

Voorbeeld:

Invoer:

4

 

O 2

 

J 2

 

T 2

 

U 2

 

 

Uitvoer:

18 3

 

O 2

 

J 2

 

T 2

 

U 2

 

OOO

 

OOO

 

OOO

 

OOO

 

OOO

 

OOO

 

JJJ

 

JJJ

 

JJJ

 

JJJ

 

TTT

 

UTU

 

UTU

 

UUU

 

TTT

 

UTU

 

UTU

 

UUU

Opgave 4. Lasca.

 

Het spel Lasca is een variant op dammen, bedacht door een vroegere wereldkampioen schaken, Emanuel Lasker. Je speelt het op een bord van zeven bij zeven vakjes. Deze vakjes zijn afwisselend gekleurd; alle hoeken zijn licht. Alleen de 25 lichte vakjes worden gebruikt; ze worden aangeduid met een hoofdletter, zie de onderstaande figuur.

 

De beide spelers beginnen met 11 stenen. Degene die begint heeft witte stenen op de vakjes A tot en met K, de ander zwarte stenen op de vakjes O tot en met Y. Er zijn ook 11 groene en 11 rode stenen; die worden later in het spel gebruikt. De groene stene horen bij de witspeler, de rode bij de zwartspeler. In de loop van het spel is er sprake van stapels; een stapel bestaat uit een of meer stenen, en behoort bij degene van wie de bovenste steen is.

Slaan; stapels maken.

Als je aan zet bent is de eerste vraag of je één of meer stapels van je tegenstander kunt slaan. Dat is het geval als het speelveld van een stapel van jou diagonaal raakt aan het speelveld van een stapel van je tegenstander staat , en er aan de andere kant van de stapel van de tegenstander een leeg speelveld is. Bij het slaan neem je de bovenste steen van de geslagen stapel af; die plaats je onder aan je eigen stapel. Als je aangekomen op het lege speelveld nog een stapel kunt slaan, dan moet je dat doen. Maar in tegenstelling tot dammen mag je met een witte of zwarte stapel alleen maar vooruit slaan! Als je op meerdere manieren kunt slaan is iedere manier toegestaan, mits je door slaat tot je niet verder kunt. Je hoeft niet te kiezen voor de zet waarmee je de meeste stapels slaat.

Zetten.

Als je niet kunt slaan moet je zetten. Je moet altijd zetten naar een aangrenzend speelveld. Je moet vooruit zetten, dat wil zeggen dat een witte stapel naar een speelveld later in het alfabet moet en een zwarte stapel naar een vakje eerder in het alfabet. Voor groene en rode stapels geldt deze beperking niet. Die mogen naar beide richtingen spelen en slaan.

Promoveren.

Als een stapel de overkant haalt wordt de bovenste steen vervangen; een witte steen wordt vervangen door een groene, een zwarte steen door een rode. Voor stapels waarvan de bovenste steen groen of rood is geldt de beperking voor de richting van het zetten en slaan niet. Maar het is niet toegestaan om in één beurt een stapel meer dan eens te slaan.

Einde van het spel.

Je hebt gewonnen wanneer je tegenstander als die aan zet is geen zet meer kan doen. Dat kan op twee manieren gebeuren: De stenen zijn op (allemaal verdwenen onder jouw stapels) of de stapels van je tegenstander staan zo dat ze niet meer kunnen zetten. Een dergelijke overwinning wordt voor het toernooi om de CvO-Windesheimprijs omgezet in een uitslag van 8-0.

Andere manieren waarop het spel kan worden beëindigd:

Als een speler maar één zet tot zijn beschikking heeft moet die worden gedaan.

Als er meerdere zetten mogelijk zijn, en er minstens vijf zetten door beide spelers gedaan zijn, mag een speler de partij opgeven. De uitslag van de partij wordt dan 7-1 in het voordeel van degene die niet opgeeft.

Beide spelers mogen eenmaal per partij remise aanbieden. Ook dit mag alleen als de speler de keuze heeft uit verschillende zetten. Accepteert de tegenstander dit remiseaanbod, dan wordt de uitslag 5-3 in het voordeel van degene die het aanbod kreeg. Zowel het remiseaanbod als de reactie erop gelden als een zet.

Als beide spelers elk vijftien zetten achter elkaar hebben gedaan zonder dat er een stapel geslagen is, of als beide spelers negentig zetten hebben gespeeld, wordt de partij afgebroken. Nu wordt voor beide partijen het aantal stapels geteld dat op dat moment op het bord staat. Als één van beide spelers meer stapels heeft dan de ander wint hij de partij met 6-2. Als beide spelers evenveel stapels op het bord hebben staan eindigt de partij in 4-4.

Het spel LASCA.EXE op de NIO-website geeft de mogelijkheid om dit spel te oefenen.

Er is ook een internationale Lascasite, op http://research.interface.co.uk/lasca

Opdracht:

Schrijf een programma NIO4 dat als invoer een bestand SPEL.IN inleest. Zo’n bestand begint met een regel met daarop het aantal z aan zetten dat er is opgenomen in dit bestand. Vervolgens komen er z regels met elk een zet van het spelverloop tot op dat moment. Een zet geeft de volledige route van een stapel aan, beginnend bij het speelveld waar de stapel is vertrokken; bijvoorbeeld HL, waarbij een stapel van vakje H naar vakje L wordt gespeeld, of AEIMQ waarbij de stapel van vakje A naar Q beweegt via de stapels op E en M en het lege vakje op I.

Remise aanbieden wordt aangeduid met een vraagteken; het antwoord daarop is de letter J of de letter N. Opgeven wordt aangegeven met de letter Z.

Je programma geeft als uitvoer een bestand SPEL.UIT. Dat bestand bestaat uit één regel. Die regel geeft een geldige zet aan in de stelling die ontstaan is na de zetten in SPEL.IN, voor de partij die aan de beurt is. Als de laatste zet van de tegenstander een remiseaanbod was is de keuze J of N. In alle andere gevallen is de keuze dus tussen een zet, een eigen remiseaanbod (mits de speler dat nog niet eerder gedaan had) of opgeven.

 

Het toernooi om de CvO-Windesheimprijs.

Dit toernooi wordt gespeeld door alle deelnemende programma’s voor opgave 4 van leerlingen en eventuele docenten. Ze spelen een volledige onderlinge competitie, die live te volgen zal zijn op het Internet. In iedere onderlinge wedstrijd zijn 8 punten te verdelen. Het doen van een ongeldige zet (verkeerde zetaanduiding, ongeldig remiseaanbod, niet ver genoeg geslagen e.d.) betekent verlies van de partij met 0-8; ook krijgt de verliezer een onreglementair partijeinde op zijn naam. Winnaar van het toernooi wordt degene met de meeste wedstrijdpunten; bij gelijk eindigen wint degene met de minste onreglementaire partijeindes op zijn naam.

 Voorbeeld:

SPEL.IN

6

 

HL

 

PLH

 

IL

 

OLI

 

?

 

N

SPEL.UIT

JM

 

 

Punten per opgave:

Opgave 1.

Goede dialoog

10 punten

Aantal regels klopt

20 punten

Aantal lampjes klopt

20 punten

Gelijkmatige verdeling

50 punten

 

Opgave 2.

Goede dialoog

10 punten 

Goede keten wanneer het lukt

30 punten

Snelste keten wanneer het lukt

15 punten

Goede getal en keten wanneer het niet lukt

30 punten

Snelste keten wanneer het niet lukt

15 punten

 

Opgave 3.

Goede dialoog

10 punten

Grootste oppervlakte

50 punten

Goede kaart

30 punten

Bestand wegschrijven

10 punten

 

Opgave 4.

Goede bestanden

10 punten 

Geldige gedwongen zet

20 punten

Geldige zet

50 punten

Plaats CvO-Windesheimtoernooi

20 punten

 

SPONSORS INFORMATICA OLYMPIADE

 

Ministerie van Onderwijs, Cultuur en Wetenschappen

KPN Telecom

Philips Eindhoven

Academic Service BV

Technische Universiteit Delft

Technische Universiteit Eindhoven

Rijks Universiteit Groningen

Universiteit Twente

Erasmus Universiteit Rotterdam

CITO Arnhem

Instituut voor Leerplanontwikkeling (SLO)

CvO Christelijke Hogeschool Windesheim