NIO 2000-2001: 1e Ronde

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 2001 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 snelle inzenders van een correcte oplossing van opgave 1. Om mee te dingen naar die prijs moet de oplossing van opgave 1 uiterlijk op 1 december 2000 binnen zijn (datum poststempel). De uitslag volgt uiterlijk 10 januari 2001. De oplossingen van alle opgaven moeten op 10 januari 2001 binnen zijn (datum poststempel). De uitslag volgt ongeveer een maand later. Deelnemers met een werkende inzending voor opgave 3 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 één archieffile. Je kunt zo'n file bijvoorbeeld maken met WinZip; een tijdelijke versie daarvan kun je downloaden vanaf de NIO-site. Neem, wanneer je niet binnen een week een ontvangstbevestiging hebt ontvangen, altijd even contact op!

De programma's:

• Gebruik een hogere programmeertaal op een MSDOS- of Windowscomputer.
• Gebruik als programmanamen NIO1, NIO2A, NIO2B en NIO3 (eventueel met een achtervoegsel dat aangeeft welke programmeertaal is gebruikt).
• Lever de programmatekst in, en zo mogelijk ook een gecompileerde versie (.EXE-bestand of .class-bestanden in JAVA).
• Een beschrijving van de opzet van het programma kan als commentaar in de programmatekst worden opgenomen.
• Gebruik het toetsenbord of een ASCII-tekstbestand voor het geven van invoer; uitvoer gaat of naar het beeldscherm of naar een ASCII-tekstbestand.
• 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!
• Alleen programma's voor opgave 3 die zonder uitvoer naar het scherm kunnen draaien kunnen meedoen aan het CvO-Windesheimtoernooi (zie de NIO-site voor aanwijzingen voor JAVA-gebruikers).
• 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.
• In Turbopascal 7.0 mag je de unit crt niet gebruiken.
• Tenzij het bij de opgave anders staat aangegeven, geldt voor ieder programma een tijdslimiet van 15 seconden op een PC met een Pentium-II met een 266 MHz processor en 64 MB intern geheugen. 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 150 van de 300 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 150 punten naar beneden bij stellen; daarom is het verstandig om, ook als je denkt niet aan de 150 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, Quick BASIC 4.5. en JAVA. Over de wijze waarop je JAVA kunt gebruiken staat informatie op de NIO-site.

Persoonlijke gegevens

Zet op de schijf een ASCII-tekstbestand 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:

Vragen en inlichtingen

Op het World Wide Web is een site met allerlei informatie over de Nederlandse Informatica Olympiade. Hier staat onder meer achtergrondinformatie bij de opgaven. Ook kunnen hier aanvullingen en verduidelijkingen worden gepubliceerd. Daarnaast is het mogelijk je in te schrijven op de NIO-mailinglist. Het adres van de website van de Nederlandse Informatica Olympiade is: http://olympiads.win.tue.nl/nio/

Je stuurt je oplossingen naar:

• Nederlandse Informatica Olympiade
• per adres Christelijke Hogeschool Windesheim
• Dienst ICT
• t.a.v. de heer Willem van der Vegt
• Postbus 10090
• 8000 GB Zwolle
• Tel. 038 4699534 (b.g.g. antwoordapparaat)
• E-mail: willem@informaticaolympiade.nl of W.van.der.Vegt@windesheim.nl

Opgave 1. Wie is de winnaar?

Een toernooi wordt gespeeld volgens een afvalsysteem. Bij aanmelding krijgt elke deelnemer een uniek volgnummer, beginnend bij 1. Voor aanvang van het toernooi worden de deelnemers op volgorde van nummer op een lijst gezet. Bij elke ronde worden er wedstrijden tussen twee deelnemers op volgorde van de lijst gespeeld; dus telkens spelen de bovenste twee spelers die nog niet gespeeld hebben tegen elkaar. De winnaar van elke wedstrijd (een gelijkspel is niet mogelijk) wordt onderaan op de speellijst voor de volgende ronde toegevoegd. Als er in een ronde een oneven aantal spelers is dan heeft de onderste speler van de lijst 'vrij'. Hij wordt automatisch geplaatst voor de volgende ronde, maar wordt dan wel bovenaan de lijst opgeschreven. Zo weet je zeker dat hij als eerste moet spelen.

Voorbeeld:

Aantal deelnemers: 11

Opdracht:

Schrijf een programma NIO1. Invoer is een tekstbestand TOERNOOI.IN met op de eerste regel het aantal deelnemers d en op de volgende d-1 regels de uitslagen van de d-1 wedstrijden. Uitvoer is het deelnemernummer van de winnaar.

Voorbeeld:

Opgave 2. Codeer en decodeer.

Een zeker codeerprogramma werkt volgens onderstaande beschrijving.

• De tekst bestaat uit een zogenaamd blok; een blok is minstens 6 en hoogstens 75 tekens lang. (In het vervolg wordt van dit blok een aantal deelblokken gemaakt.)
• Herhaal voor ieder (deel)blok de volgende stappen tot het (deel)blok uit maximaal 2 tekens bestaat:
• Maak twee deelblokken, het eerste bestaat uit de tekens die op de oneven plaatsen in het oorspronkelijke (deel)blok staan, het tweede uit de tekens die op de even plaatsen in het oorspronkelijke (deel)blok staan.
• Voeg nu de zo verkregen blokken samen tot één gecodeerde tekst.

Voorbeeld: Het blok "computer" wordt op deze manier "cumeotpr"

en het blok "INFORMATICA OLYMPIADE" wordt op deze manier "IPIREOFAAAYNICMLOD TM"

Opdracht 2A:

Schrijf een programma NIO2A dat een tekstbestand NORMAAL.TXT inleest. Dat is een tekst van minstens 6 en maximaal 75 tekens op één regel. Uitvoer is een bestand GEHEIM.TXT met de op de hierboven beschreven gecodeerde tekst.

Opdracht 2B:

Schrijf een programma NIO2B dat een tekstbestand GEHEIM.TXT inleest. Dat is een tekst van minstens 6 en maximaal 75 tekens op één regel. Uitvoer is een bestand NORMAAL.TXT; uiteraard moet dit het bestand zijn dat bij gebruik van programma NIO1A weer dezelfde GEHEIM.TXT oplevert.

Op de NIO-site tref je een applet aan die de werking van programma NIO2A nabootst.

Opgave 3. Susan.

Het spel Susan is bedacht door Stephen Linhart in 1991. Informatie over de ontstaansgeschiedenis en aanwijzingen over het spel kun je vinden op http://www.stephen.com/sue/sue_man.txt

Je speelt Susan met twee personen op een zeshoekig spelbord van 61 vakjes. De meeste vakjes hebben zes buren, de randvakjes hebben er vier en de hoekvakjes hebben drie buren. Vakjes worden aangeduid met een combinatie van letter en cijfer, zie onderstaande figuur.

Het spelbord van Susan.

Beide spelers hebben een stapel stenen, de ene rood, de ander geel. Degene met de rode stenen mag beginnen, daarna zetten de spelers om beurten. Als je aan de beurt bent mag je een steen op het bord plaatsen op een leeg vakje, of je mag een steen van jezelf die al op het bord stond verschuiven naar een leeg buurvakje. Als beide spelers drie maal achter elkaar een steen hebben verschoven (dus in totaal zes keer schuiven) is het remise. Je mag geen beurt overslaan.

Het doel van het spel is het insluiten van één van de stenen van je tegenstander. Je sluit een steen in door alle ruimtes er om heen te vullen; een steen kan worden ingesloten door iedere combinatie van jouw stenen, de stenen van je tegenstander en de rand van het spelbord. Maar pas op: Als één van jouw stenen door je zet wordt ingesloten, verlies je het spel, ook al heb je tegelijkertijd een steen van je tegenstander ingesloten.

Enkele voorbeelden.

(In de figuren worden rode stenen met een horizontale band aangegeven en gele met een verticale band.)

Bedreigd:

De rode steen op e4 is aan vijf kanten omringd; rood moet een verdedigende zet doen, anders zal geel bij de volgende zet winnen.

Verdedigd:

Rood zet op d2 en beschermt zo tegen het plaatsen van een steen op e3. Als geel nu op e3 zet verliest hij, omdat beide spelers dan een ingesloten steen hebben.

Blokkade:

Als geel nu zijn steen van d3 naar e3 verschuift is het voor beide spelers onhandig om een steen op d3 te plaatsen, omdat dat beide spelers tegelijk een ingesloten steen krijgen.

Opdracht:

Schrijf een programma NIO3 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 steen plaatsen wordt aangegeven door de aanduiding van het lege vakje te geven (bijvoorbeeld e3 of c6), bij een steen verschuiven wordt eerst het oorspronkelijke vakje aangegeven, vervolgens een min-teken, dan het nieuwe vakje (bijvoorbeeld e3-f2).

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 je nog kunt zetten zonder remise te maken of te verliezen moet je dat doen.

Het toernooi om de CvO-Windesheimprijs.

Dit toernooi wordt gespeeld door alle deelnemende programma’s voor opgave 3 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 2 wedstrijdpunten te verdelen; bij winst gaan die punten naar de winnaar, bij remise krijgen beide deelnemers één punt. Het doen van een ongeldige zet (verkeerde zetaanduiding, plaatsen op een bezet vakje e.d.) betekent verlies van de partij; daarbij krijgt de verliezer een onreglementair partijeinde op zijn naam. Ook zijn er per partij 200 zetpunten te verdelen. De verliezer krijgt één punt voor iedere zet uit de partij, de winnaar 200 punten min het aantal zetten. Na 99 zetten wordt de partij door het juryprogramma afgebroken. Als er dan nog geen steen is ingesloten eindigt de partij in remise. Bij elke remise ontvangen beide spelers 100 zetpunten.

Winnaar van het toernooi wordt degene met de meeste wedstrijdpunten. Bij gelijk eindigen in wedstrijdpunten wint degene met het meeste zetpunten. Als ook dat geen beslissing oplevert wint degene die de minste onregelmatige partijeindes heeft gehad. Als ook dat niet helpt eindigen de deelnemers op dezelfde plaats.

 Voorbeeld:

Punten per opgave:

Opgave 1.

Opgave 2.

 Opgave 3.

Ministerie van Onderwijs, Cultuur en Wetenschappen

Philips Electronics

Academic Service BV

Technische Universiteit Delft

Technische Universiteit Eindhoven

Rijks Universiteit Groningen

Universiteit Twente

Erasmus Universiteit Rotterdam

Instituut voor Leerplanontwikkeling (SLO)

CvO Christelijke Hogeschool Windesheim