2001-2002

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 2002 niet ouder zijn dan 20 jaar.

Het inzenden van je oplossingen

De oplossingen van alle opgaven moeten op 10 januari 2002 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 250 Euro, beschikbaar gesteld voor de leerling of docent die het toernooi bij deze opgave weet te winnen. Als extra stimulans zijn er prijzen voor snelle inzenders van een correcte oplossing van opgave 1 (dat wil zeggen dat je programma tenminste 60 van de 100 punten haalt): een hoofdprijs ter waarde van 500 Euro en 5 troostprijzen van 100 Euro. Om mee te dingen naar die prijs moet de oplossing van opgave 1 uiterlijk op 1 december 2001 binnen zijn (datum poststempel). De uitslag volgt uiterlijk 10 januari 2002. Zend je oplossing in op twee 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, NIO2 en NIO3 (eventueel met een achtervoegsel dat aangeeft welke programmeertaal is gebruikt). Lever de programmatekst (broncode) 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.
• Lees de invoer uit een ASCII tekstbestand; schrijf de uitvoer naar een ASCII-tekstbestand. Bij opgave 2 is helemaal geen in- of uitvoer!
• Je programma mag geen bijzondere eisen stellen aan de hardware van de jury; het wordt getest op een Pentium-III met een 700 MHz processor en 128 MB intern geheugen en voldoende harde schijfruimte. Je programma zal worden gestart in een eigen directory, waar het lees- en schrijfrechten heeft.
• Je programma mag geen uitvoer naar het scherm schrijven en niet op invoer van het toetsenbord wachten.
• In Turbo Pascal 7.0 mag je de unit crt niet gebruiken.
• Tenzij het bij de opgave anders staat aangegeven, geldt voor ieder programma een tijdslimiet van 5 seconden op een PC met een Pentium-III met een 700 MHz processor en 128 MB intern geheugen. Als je programma meer tijd nodig heeft dan de tijdslimiet voor een bepaald probleem, dan scoort je programma voor dit probleem geen punten.

Waardering en vervolg

Voor iedere opgave kun je maximaal 100 punten verdienen. Bij elke opgave staat de 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 bijstellen; 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 de volgende programmeertalen toegestaan: Turbo C++, GNU C++, Turbo Pascal, FreePascal, Quick BASIC 4.5, Visual Basic en JAVA. Over de wijze waarop je deze talen kunt gebruiken komt 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 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://www.informaticaolympiade.nl/

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
• E-mail: willem@informaticaolympiade.nl of W.van.der.Vegt@windesheim.nl

Opgave 1. Eerlijk delen

Een groep kinderen heeft spullen meegenomen naar de vrijmarkt. Van alles wat ze willen verkopen hebben ze een prijs vastgesteld. Na afloop hebben ze een deel van hun spullen over. Ze willen wat ze over hebben eerlijk verdelen: Iedereen moet voor dezelfde waarde aan spullen mee naar huis nemen. Wat niet verdeeld kan worden blijft op de vrijmarkt achter; uiteraard willen ze dat dat zo weinig mogelijk waard is. Voor het gemak worden zowel de kinderen als de artikelen oplopend genummerd vanaf 1.

Opdracht:

Schrijf een programma NIO1. Invoer is een bestand SPULLEN.IN. Op de eerste regel daarvan staat een getal k, dat aangeeft uit hoeveel kinderen de groep bestaat; 1 < k < 10. Op de tweede regel staat een getal s dat aangeeft hoeveel spullen te verdelen zijn; 3 < s < 100. Op de volgende s regels staan de waardes van de spullen (in eurocenten); een waarde is een getal w waarvoor geldt 0 < w < 1000.

Je programma geeft als uitvoer een bestand SPULLEN.UIT. Dit bestand bestaat uit s regels. Op iedere regel staat aangegeven wie het betreffende artikel meeneemt; er staat een 0 als het artikel niet mee naar huisgenomen wordt en dus achterblijft. De som van de waardes van de artikelen die achterblijven moet zo klein mogelijk zijn, en de som van de waardes van de artikelen die ieder kind meeneemt moet voor iedereen gelijk zijn.

Opgave 2. Sorteren

Je hebt een stapel kaartjes van verschillende grootte. Grotere kaartjes steken uit achter kleinere, kleinere achter grotere zijn niet te zien. Om deze kaartjes in oplopende grootte te sorteren, kun je een sorteerhulpmachine gebruiken. Je kunt de sorteerhulpmachine een bepaalde kaartjesvolgorde geven, hij geeft dan aan welke kaartjes te zien zijn.De kaartjes worden aangeduid met een kleine letter. Er zijn er minstens 4, hoogstens 26. Bij n kaartjes worden de eerste n letters uit het alfabet gebruikt om ze een naam te geven.

Opdracht:

Schrijf een programma NIO2 dat gebruik maakt van een unit of hulpprogramma SHM (sorteerhulpmachine). Voor verschillende talen is zo'n programma beschikbaar; zie voor verdere technische informatie de NIO-Website (via de link Aanvullingen en errata).

Beschikbaar zijn drie functies:

Je programma moet gebruik maken van de functies van SHM en op een efficiënte manier de volgorde van de kaartjes achterhalen. Als je een volgorde voorstelt die niet kan kloppen met de voorafgaande antwoorden kost dat per test 3 (van de 10) punten; als je meer dan n keer moet proberen om het goede antwoord te vinden krijg je geen punten voor de oplossing.

Om je programma te testen kun je een bestandje SHM.IN maken met daarin een "goede volgorde". Let op dat je programma GEEN invoer hoeft te lezen, of uitvoer mag schrijven!

Hieronder zie je in enkele plaatjes aangegeven hoe de oplossing van dit voorbeeld werd bereikt.

De te vinden volgorde (uit bestand SHM.IN).

De eerste poging.

De tweede poging.

De derde en laatste poging.

Opgave 3. Dao

Dao is een bordspel dat wordt gespeeld op een bord van vier bij vier vakjes. De twee spelers, rood en blauw, hebben elk vier stenen, die aan het begin van het spel op een diagonaal staan. De vakjes worden aangeduid met een letter en een cijfer; zie de figuur hieronder.

De spelers zetten om beurten; rood begint (rood wordt in de figuur ook aangeduid met een kruis). Een zet bestaat er uit dat je één van de stenen van jouw kleur oppakt en zo ver je kunt opschuift, horizontaal of vertikaal. Daarbij mag je uitsluitend lege vakjes overslaan. Een steen die je hebt gezet staat na die zet tegen de rand van het bord of naast een andere steen. In de beginopstelling kan blauw met de steen van b3 dus uitsluitend naar a3 of naar b4. De rode steen op a1 kan bijvoorbeeld alleen naar a3 of naar c3.

Het spel is beslist als één van de volgende vijf situaties zich voordoet:

Het spel is remise als één van de volgende twee zaken zich voordoet:

Het spel DAO is ontwikkeld door Jeff Pickering en Ben Van Bushkirk (zie ook http://www.playdao.com); onze versie wijkt af van de oorspronkelijke omdat diagonaal zetten in deze opgave niet is toegestaan.

Een programma waarmee je DAO met onze spelregels kunt spelen staat op de NIO-Website (via de link Aanvullingen en errata).

Opdracht:

Schrijf een programma NIO3 dat als invoer een bestand DAO.IN inleest. Zo’n bestand begint met een regel met daarop het aantal zetten (z) dat is opgenomen in dit bestand. Vervolgens komen er z regels met op elke regel een zet. Een zet wordt aangegeven door eerst het oorspronkelijke vakje aan te geven, vervolgens een min-teken, dan het nieuwe vakje (bijvoorbeeld a3-a2).

Je programma geeft als uitvoer een bestand DAO.UIT. Dat bestand bestaat uit één regel. Die regel geeft een geldige zet aan voor de speler die aan de beurt is. Een zet is geldig als die is toegestaan na de zetten in DAO.IN. Als je nog kunt zetten zonder onmiddellijk daarna te verliezen moet je dat doen. Als je dat niet doet wordt dit een ‘onnodig verlies’ genoemd.

Het toernooi om de CvO-Windesheimprijs.

Dit toernooi wordt gespeeld door alle deelnemende programma’s voor opgave 3 van leerlingen en eventueel docenten. Ze spelen een volledige onderlinge competitie, die live te volgen zal zijn op het Internet. In iedere onderlinge wedstrijd zijn wedstrijdpunten te verdienen; bij winst gaan er drie punten naar de winnaar (en geen naar de verliezer), 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 400 zetpunten te verdelen. De verliezer krijgt één punt voor iedere zet uit de partij, de winnaar 400 punten min het aantal zetten. Na 200 zetten wordt de partij door het juryprogramma afgebroken. Als er dan nog geen winnaar is eindigt de partij in remise. Bij elke remise ontvangen beide spelers 200 zetpunten.

Winnaar van het toernooi is degene met de meeste wedstrijdpunten. Als meerdere spelers een gelijk aantal wedstrijdpunten punten hebben, wint degene met de 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.

Je programma wordt vooraf door de organisatie getest. Als het in staat is samen te werken met de wedstrijdsoftware wordt het toegelaten tot het toernooi. Als dat niet het geval is krijg je altijd bericht, en wordt het programma apart gejureerd.

Voorbeeld:

Punten per opgave:

Opgave 1.

10 testgevallen. Per testgeval:

Opgave 2.

10 testgevallen. Per testgeval:

 Opgave 3.

Als je programma wordt toegelaten tot het toernooi om de CvO-Windesheimprijs:

 Als je programma niet wordt toegelaten: (bijvoorbeeld omdat het niet samenwerkt met de jurysoftware)

5 testgevallen. Per test:

Ministerie van Onderwijs, Cultuur en Wetenschappen

Philips Electronics

Eljakim Information Technology BV

Technische Universiteit Delft

Technische Universiteit Eindhoven

Rijks Universiteit Groningen

Universiteit Twente

Instituut voor Leerplanontwikkeling (SLO)

CvO Christelijke Hogeschool Windesheim