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 1998 niet ouder zijn dan 19 jaar en in het leerjaar 1998/1999 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 1997 binnen zijn (datum poststempel). De uitslag volgt voor 10 januari 1998. De oplossingen van alle opgaven moeten op 15 januari 1998 binnen zijn (datum post- stempel). 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,-, 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. Ook inzenden via E-mail is mogelijk; zend alle gevraagde bestanden in één archieffile, bij voorkeur een self-extractor. Neem wanneer je niet binnen een week een ontvangstbeves- tiging hebt ontvangen altijd even contact op! De programma's: - Gebruik een hogere programmeertaal op een MS-DOS-computer. - Gebruik als programmanamen NIO1, NIO2A, NIO2B, NIO3 en NIO4 (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 (of als dat aangegeven staat 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! - Opgave 2 en 4 worden automatisch gejureerd. Daarom moet je je bij deze opgaven houden aan de technische randvoorwaarde (zie onder opgave 4). - 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. - Tenzij het bij de opgave anders staat aangegeven geldt voor ieder programma een tijdslimiet van 15 seconden op een PC met een Pentium 75 processor. Oplossin- gen 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 World Wide Web is een site met allerlei informatie over de Nederlandse Informati- ca Olympiade. Het adres daarvan is: http://www.win.tue.nl/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 (bgg antwoordapparaat) E-mail: W.van.der.Vegt@chw.nl Opgave 1. Een geldige formule *** hier een afbeelding bij van vier blokjes met getallen en drie blokjes met operatoren *** Je kunt van een getal een formule maken door tussen twee opvolgende cijfers telkens één van de symbolen +, -, * (voor vermenigvuldigen), / (voor delen) of = te zetten. Zo'n formule wordt een geldige formule genoemd wanneer maar één is-gelijk-teken wordt gebruikt; aan weerszijden van dat is-teken moet de berekening op hetzelfde getal uitkomen, en dat mag niet 0 zijn. De bewerkingen worden in volgorde uitgevoerd, dus bijvoorbeeld 6/3*2 levert (6/3)*2 op oftewel 4, en 6+4/2 levert (6+4)/2 is 5 op. Je mag bij het maken van formules geen haakjes gebruiken. Schrijf een programma dat als invoer een getal van vier cijfers inleest (het getal begint niet met een 0). Het programma geeft als uitvoer een regel met indien mogelijk een geldige formule bij het getal, anders de tekst "kan niet". Voorbeelden: Invoer 5381 Uitvoer 5 + 3 = 8 * 1 Invoer 1205 Uitvoer kan niet Opgave 2. De waslijnen *** hier een afbeelding van een serie waslijnen met wasgoed *** Een bedrijfje heeft 100 waslijnen van elk 200 centimeter. Een andere firma biedt elke dag enkele wasmanden vol nat wasgoed aan; een medewerker pakt de was stuk voor stuk uit en hangt deze meteen aan een lijn. Hij probeert daarbij zo min mogelijk lijnen te gebrui- ken. Opdracht A: Schrijf een programma dat in een voortdurende dialoog vraagt om een stuk wasgoed, de breedte daarvan in centimeters inleest (dat is een geheel getal, niet groter dan 200) en aangeeft aan welke waslijn (genummerd van 1 tot en met 100) dit wasgoed wordt opgehangen. Invoer van een breedte 0 geeft aan dat alle was hangt. Als uitvoer geeft het programma dan tenslotte het aantal gebruikte waslijnen aan. De breedte van de totale was is minder dan 10000 centimeter. Voorbeeld: Breedte: 120 Waslijn: 1 Breedte: 175 Waslijn: 2 Breedte: 100 Waslijn: 3 Breedte: 25 Waslijn: 2 Breedte: 77 Waslijn: 1 Breedte: 0 Lijnen: 3 Met een programma dat volgens deze specificatie werkt en niet meer dan 100 lijnen nodig heeft, verdien je 50 punten. Nog eens 20 punten zijn te verdienen met een werkwijze die, gerekend over een aantal tests, in de meeste gevallen efficiënt werkt. Daarvoor moet je programma in de helft van de testgevallen niet meer dan twee lijnen meer gebruiken dan het beste programma bij dat testgeval. Opdracht B: Een andere medewerker pakt eerst alle was uit, en gaat dan de lijnen zo efficiënt mogelijk gebruiken. Schrijf voor deze medewerker een programma dat eerst alle was inleest (in de vorm van een serie van maximaal 10000 getallen, afgesloten met een 0), en vervolgens bepaalt hoeveel waslijnen minimaal nodig zijn. Voorbeeld: Breedte: 120 Breedte: 175 Breedte: 100 Breedte: 25 Breedte: 77 Breedte: 0 Lijnen: 3 Houd je bij deze opgave aan de technische randvoorwaarde die staat beschreven na opgave 4. De tijdlimiet waarbinnen je programma voor opdracht A na invoer van de breedte van een stuk wasgoed moet reageren is 5 seconden. Opgave 3. Duitse kentekens in Nederland *** Hier de afbeelding van een kentekenplaat of een plaatsnaambord o.i.d. *** In Duitsland beginnen de kentekens van auto's met een code die aangeeft uit welke plaats of welke streek ze komen. Hoe zou dat voor Nederland of delen van Nederland uitpakken? Een plaatscode is een tekst van één, twee of drie letters. De eerste letter is altijd de eerste letter van de plaatsnaam. Voor de eventuele tweede en derde letter zijn er verschillende mogelijkheden. Om die van elkaar te onderscheiden hoort bij iedere toegestane plaatscode een codewaarde. Zie het overzicht hieronder. Een plaatsnaam is opgebouwd uit (vb APELDOORN): Eerste letter A Tweede letter P Laatste letter N Derde letter E Voorlaatste letter R Medeklinker P,L,D,R Klinker E,O,O Medeklinkers en klinkers zijn dus een lijst, waaruit je iedere letter zo vaak mag gebruiken als deze voorkomt. De derde en voorlaatste letter tellen ook als medeklinker of klinker; ze zijn elk slechts in één combinatie meer waard. Plaatscode Codewaardering Voorbeeld Eerste letter 15 A Eerste letter, tweede letter 14 AP Eerste letter, laatste letter 13 AN Eerste, tweede en derde letter 12 APE Eerste, tweede, laatste letter 11 APN Eerste, voorlaatste, laatste letter 10 ARN Eerste letter, medeklinker 9 AP, AL, AD, AR Eerste letter, klinker 8 AE, AO Eerste, tweede letter, medeklinker 7 APL, APD, APR Eerste, tweede letter, klinker 6 APE, APO Eerste letter, medeklinker, laatste 5 ALN, ADN Eerste letter, klinker, laatste 4 AEN, AON Eerste letter, twee medeklinkers 3 ALD, ALR, ADR Eerste letter, klinker en medeklinker AEL, AED, AER, of medeklinker en klinker 2 ALO, ADO, AOR Eerste letter, twee klinkers 1 AEO, AOO De letters staan in een plaatscode op dezelfde volgorde als in de plaatsnaam! AOD voor Apeldoorn kan dus niet. Schrijf een programma dat om de naam van een invoerbestand vraagt. Dat invoerbestand begint met een regel waarop staat hoeveel plaatsen er in het bestand voorkomen (minstens 1, hoogstens 1000); vervolgens staat op iedere regel in het bestand een plaatsnaam. Een plaatsnaam is een woord zonder spaties of leestekens, geheel geschre- ven in hoofdletters. Plaatsen als LAGE ZWALUWE of 'S GRAVENHAGE komen dus niet in het bestand voor. Plaatsnamen bestaan uit maximaal 20 tekens. Iedere plaats krijgt de nog beschikbare code met de hoogste codewaarde, maar met één voorwaarde: Deze code mag niet met minstens dezelfde codewaarde kunnen worden gebruikt bij één van de eerder in het bestand genoemde plaatsen. Als LEIDEN code L krijgt en later in het bestand LEEUWARDEN staat, krijgt LEEUWARDEN niet de code L, omdat die al vergeven is, maar ook niet LE of LN, omdat die codes bij LEIDEN ook 14 of 13 waard zouden zijn geweest. De keuze voor LEEUWARDEN wordt daarom LEE, codewaarde 12. Bij verschillende alternatieven met dezelfde codewaarde kies je de eerste op alfabet. Als je bij APELDOORN kunt kiezen tussen AEL, AED en ADO dan kies je voor ADO. Als uitvoer schrijf je een bestand NIO4.UIT, met daarin de gebruikte codes; voor elke plaats in de invoer gebruik je één regel, zo mogelijk voor de code. Als je geen code aan de plaats kunt toekennen, gebruik je een min-teken. Zie voor de uitvoer ook het voor- beeld. Voorbeeld: Naam invoerbestand: H.IN Inhoud invoer: 18 Code waarde HAAG H 15 HAARLEM HM 13 HILVERSUM HI 14 HERTOGENBOSCH HE 14 HEERLEN HN 13 HENGELO HO 13 HEERENVEEN HV 9 HOOGEVEEN HOO 12 HOOGEZAND HD 13 HINDELOOPEN HIN 12 HASSELT HT 13 HATTEM HAT 12 HEERDE HDE 10 HENGEVELDE HNE 5 HEILOO HEI 12 HEINO HNO 10 HEE - 0 HAREN HAR 11 Uitvoer in NIO4.UIT H HM HI HE HN HO HV HOO HD HIN HT HAT HDE HNE HEI HNO - HAK De tijdlimiet voor deze opgave is 15 seconden per 100 plaatsen of een gedeelte ervan, dus bij 200 plaatsen 30 seconden, bij 201 plaatsen 45 seconden, etc. Opgave 4. Tac-Tic-Turn Het spel Tac-Tic-Turn wordt gespeeld door twee spelers op een speelveld van drie bij drie plateautjes (zie figuur 1 en 2). Op ieder plateautje zijn vier uitsparingen voor stenen; zo passen er 36 stenen op het hele speelbord. Beide spelers, Rood en Zwart, hebben 18 stenen van hun eigen kleur. Doel van het spel is zo snel mogelijk vier stenen van de eigen kleur op een aansluitende ononderbroken rij te hebben, horizontaal, verticaal of diagonaal. De spelers doen om beurten een zet; Rood begint. Er zijn twee soorten zetten mogelijk: 1. Het plaatsen van een nieuwe steen in een uitsparing. 2. Het draaien van een plateautje. De stenen op het plateautje blijven hun onderlin- gen positie houden, maar de positie ten opzichte van de andere stenen op het speelveld kan zo veranderen. Een plateautje dat door één van beide spelers is gedraaid, mag niet in de meteen volgende zet door de tegenstander worden gedraaid. Als door het draaien van een plateautje beide partijen een rij van vier stenen krijgen wint degene die niet zelf draaide. Als elk van beide spelers vijftig zetten heeft gedaan en nog geen van beiden een rij van vier heeft is de partij geëindigd in remise. Notatie: De plateautjes worden aangegeven met de hoofdletters A tot en met I. De posities van de uitsparingen met kleine letters a,b,c en d (rechtsboven is a, met de klok mee). Bij het plaatsen van een steen wordt de positie van de lege uitsparing aangegeven (bijvoorbeeld Ed). Bij draaien wordt het plateautje aangegeven, gevolgd door een getal dat aangeeft hoeveel rechte hoeken het gedraaid wordt (1, 2 of 3, gerekend met de klok mee). Schrijf een programma dat een stelling van Tic-Tac-Turn inleest van het toetsenbord (zie hieronder en het voorbeeld). Als uitvoer geeft het programma een zet voor de partij die aan zet is, of de melding dat één van beide partijen gewonnen heeft (uitvoer R of Z), of dat het remise is (uitvoer O van onbeslist). Ad Aa Bd Ba Cd Ca Ac Ab Bc Bb Cc Cb Dd Da Ed Ea Fd Fa Dc Db Ec Eb Fc Fb Gd Ga Hd Ha Id Ia Gc Gb Hc Hb Ic Ib Figuur 1. Het speelveld van Tic-Tac-Turn. Hoofdletters voor plateautjes, kleine letters voor uitsparingen. *** Figuur 2 is de schets van een plateautje, voorbeeld bijgevoegd *** Een stelling wordt weergegeven in negen regels; eerst wie er aan zet is, vervolgens de laatste zet (of een minteken voor de lege beginstelling), daarna het aantal zetten dat Rood gedaan heeft, en tenslotte in zes regels van zes tekens de stelling. R en Z staan voor de stenen van Rood en Zwart, een stip voor een lege uitsparing. Voorbeeld: Z Zwart aan zet G1 Laatste zet was plateautje G kwartslag draaien 20 Rood heeft 20 zetten gedaan RZ..RR RZZ... .....Z ...... RZRZRZ ZRRZZZ Uitvoer: H1 gevolg van deze zet is winst voor Zwart Het toernooi om de CvO-Windesheimprijs Goed werkende programma's nemen deel aan het toernooi om de CvO-Windesheimprijs. Alle deelnemende programma's spelen, eventueel na voorrondes, twee wedstrijden tegen elk van de andere deelnemers, een keer met Rood en een keer met Zwart. Winst levert 2 wedstrijdpunten op, gelijkspel 1, verlies 0. Als deelnemers gelijk eindigen 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 juryprogramma omgevormd tot een stelling, die door het programma dat Zwart heeft als invoer gebruikt, en zo wordt de stelling tussen beide programma's heen en weer gescho- ven 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 voor opgaven 2 en 4 Om deelnemende programma's aan het toernooi om de CvO-Windesheimprijs op een goede manier tegen elkaar te laten spelen en om opgave 3 goed te kunnen jureren is het van belang dat bij in- en uitvoer standaard input en output worden gebruikt! Dat betekent bijvoorbeeld in TurboPascal geen unit crt gebruiken en in TurboC 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 "NIO5 < IN.TST > UIT.TST", waarbij NIO5 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. Uiteraard test de jury of je bij opgave 2A in- en uitvoer elkaar wel in de goede volgorde laat opvolgen! Punten per opgave: Opgave 1. Goede dialoog: 20 punten Goede som gevonden: 80 punten Opgave 2. Goede dialoog: 10 punten Technische randvoorwaarde: 10 punten Correcte afhandeling 2A: 30 punten Beste oplossing 2A: 20 punten Beste oplossing 2B: 30 punten Opgave 3. Goede dialoog: 10 punten Goede codes gevonden: 80 punten Bestand wegschrijven: 10 punten Opgave 4. Goede dialoog: 10 punten Technische randvoorwaarde: 10 punten Geldige zet: 30 punten Einde partij vaststellen: 15 punten Onbeslist vaststellen: 15 punten Plaats CvO-Windesheimtoernooi: 20 punten Totaal 400 punten