Voorwaarden en aanwijzingen. De Nederlandse Informatica Olympiade is een wedstrijd voor leerlingen uit het voortgezet onderwijs. De leerling mag op 1 juli 1996 niet ouder zijn dan 19 jaar en moet in het leerjaar 95/96 op een VBO, MAVO, HAVO of VWO zitten. Het inzenden van je oplossingen. De oplossingen moeten op 15 januari 1996 binnen zijn (datum poststempel). De uitslag volgt ongeveer een maand later. 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 beiden 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. De programma's. Op je diskette staan de programma's met de namen NIO1, NIO2, NIO3 en NIO4 (eventueel met een achtervoegsel dat aangeeft welke programmeertaal is gebruikt). Je levert in ieder geval de programmatekst, zo mogelijk ook een gecompileerde versie (bij talen zoals Pascal en BASIC). In de programma- tekst kun je in de vorm van commentaar een beschrijving opnemen van de opzet van het programma. Je programma dient op het beeldscherm aanwijzingen te geven die de gebruiker duidelijk maken welke invoer wordt verwacht. Wanneer je programma bijzondere eisen stelt aan de hardware (bijvoorbeeld een speciale grafische kaart) moet je dat duidelijk aangeven, bij voorkeur in de eerste tekst die het programma presenteert of anders in het commentaar aan het begin van de programmatekst. Wanneer je bij het uitwerken van een programma een eigen interpretatie hebt moeten geven van de opgave is het verstandig daarover in de tekst die het programma op het beeldscherm presenteert melding van te maken. De jury kan daar dan rekening mee houden. Waardering en vervolg. Voor iedere opgave kun je maximaal 100 punten verdienen. Na de opgaven staat een puntenverdeling aangegeven. De jurypunten bij iedere opgave zijn bedoeld om fraaie, snelle of originele oplossingen extra te kunnen honore- ren. 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 heeft het recht deze grens van 200 punten naar beneden bij te stellen als de uitkomsten van de eerste ronde dat noodzakelijk maken. Tijdens de tweede ronde zijn (evenals op de Internationale Informatica Olympiade) alleen de volgende programmeertalen toegestaan: Turbo C++ versie 3.0, Turbopascal 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 van PERSGEG.1, PERSGEG.2 enz. te worden vastgelegd: op regel 1 je naam (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: 760321 (voor 21 maart 1976)) 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 bulletinboard SLO-Lijn is een apart gebied beschikbaar voor deelne- mers aan de Nederlandse Informatica Olympiade. Hier zijn bijvoorbeeld uitwerkingen te vinden van opgaven uit vorige jaren. Je kunt hier ook vragen deponeren over de opgaven; je krijgt dan binnen een week een reactie. Het telefoonnummer van SLO-Lijn is 053 341634. De instellingen van je modem moeten zijn: Geen pariteit, 8 databits en 1 stopbit. 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 Opgave 1. Weg met die postzegels. Een vakantiewerker op een kantoor met een rustige postkamer besluit de verzameling postzegels eens wat uit te dunnen. Bij ieder poststuk dat moet worden verzonden plakt hij zo veel mogelijk postzegels, tot hij aan het goede bedrag zit, of als dat niet kan er zo dicht mogelijk overeen komt. Na een poosje is hij door de kleinste zegels heen. Inmiddels kan hij wel wat hulp gebruiken. Schrijf een programma waarin je een serie postzegels kunt inlezen en een bedrag dat je wilt frankeren. Het programma geeft nu een lijstje met postze- gels uit je verzameling die je moet gebruiken. Het moet niet met meer postzegels kunnen. Voorbeeld: Geef postzegels, afgesloten met een 0. 25 25 25 25 50 50 100 0 Te frankeren bedrag: 72 Te gebruiken: 25 25 25 Goedkoper kan niet, met meer dan 3 zegels lukt ook niet. Opgave 2. Julius gekraakt! Al in de tijd van de Romeinen werd de volgende eenvoudige code gebruikt. Spreek met degene naar wie je berichten verstuurt een codegetal af (tussen de 1 en de 25), en doe voor elke letter van het bericht dat je wilt versturen het volgende. Tel in het alfabet zoveel letters verder als wordt aangegeven door het codegetal (wanneer je voorbij de Z zou moeten ga je weer verder met de A). Spaties en leestekens blijven onveranderd; bijzondere letters (‚ of €) komen niet in de tekst voor. Voorbeeld: Codegetal 7, boodschap TEKST Gecodeerde boodschap ALRZA Schrijf een programma voor het ontcijferen van berichten in deze code. Daarbij mag je er van uit gaan dat er alleen hoofdletters in teksten voor- komen; een gecodeerde (te ontcijferen) boodschap staat in een ASCII- tekstfile die uit maximaal 10 regels van maximaal 80 tekens bestaat. Je programma vraagt om de naam van zo'n tekstfile, beeldt de inhoud ervan op het scherm af en doet daaronder een voorstel voor de ontcijfering ervan. Daarbij mag je er van uitgaan dat letters en lettercombinaties in een bericht ongeveer even vaak voorkomen als in andere Nederlandstalige teksten. Naam tekstbestand: TEST.IN Gecodeerde bericht: GLW LU HHQ HHQYRXGLJH WHVW. SUREHHU RI MH GRRU GH IUHTXHQWLH YDQ GH OHWWHVV WH WXUYHQ NXQW YLQGHQ ZDW GH H LV. CR LHWV! Vertaling: DIT IS EEN EENVOUDIGE TEST. PROBEER OF JE DOOR DE FREQUENTIE VAN DE LETTERS TE TURVEN KUNT VINDEN WAT DE E IS. ZO IETS! Opgave 3. Opname planning. Binnen een grote onderwijsinstelling bestaat de mogelijkheid om televisie- programma's te laten opnemen. De school heeft zes videorecorders die elk dezelfde 20 televisiekanalen kunnen ontvangen. Docenten leveren uiterlijk de dag voor de opname een briefje in waarop staat hoe laat het programma dat ze willen opnemen begint, hoelang het duurt en op welk kanaal het te ontvangen is (Vb "12:30 45 3" betekent dat er om 12:30 u. een programma van 45 minuten begint op kanaal 3). De opname assistent stelt 's morgens de beschikbare recorders zo in dat hij er de rest van de dag geen omkijken meer naar heeft. Hij wil zo veel mogelijk gebruik maken van al gebruikte banden en eventueel niet alle recorders gebruiken als het niet nodig is. Omdat dat af en toe een heel gepuzzel is, zoekt hij een programma dat hem bij die planning kan helpen. Schrijf een programma dat eerst de wensen van de docenten voor opnames voor een bepaalde dag inleest (zie hieronder). Vervolgens worden de gege- vens over de eventueel nog te gebruiken banden ingelezen, met de beschik- bare ruimte die ze nog hebben (in minuten). De opname assistent heeft onbeperkt de beschikking over nieuwe banden, elk met een opnamecapaci- teit van 240 minuten. Het programma maakt een lijst met telkens per videorecorder het nummer van de te gebruiken band en het aantal op te nemen programma's, gevolgd door voor ieder programma een regel met daarop aanvang, duur en kanaal van het programma. Voorbeeld. Aantal opnamewensen: 6 Op te nemen: 10:00 40 1 10:30 30 2 10:40 60 3 10:45 20 1 11:00 120 4 11:30 40 2 Aantal vrije banden: 2 Minuten op band 1: 90 Minuten op band 2: 60 Opnameschema: 3 recorders, 2 nieuwe banden Recorder 1 band 2 aantal 2 10:45 20 1 11:30 40 2 Recorder 2 band 3 aantal 2 10:00 40 1 10:40 60 3 Recorder 3 band 4 aantal 2 10:30 30 2 11:00 120 4 Merk op dat er geen schema is waarbij minder dan twee nieuwe banden hoeven te worden gebruikt. In de verzameling schema's met twee nieuwe banden is er geen schema te vinden met minder dan drie recorders. Dus dit is ‚‚n van de goede oplossingen. Als er geen kloppend schema kan woren gemaakt is de uitvoer van het programma: "Geen indeling mogelijk!". Alleen programma's tussen 10:00 en 24:00 worden opgenomen. Een opgenomen programma moet in zijn geheel op ‚‚n band terecht komen. Je hoeft geen rekening te houden met extra opnametijd in verband met moge- lijke uitloop van programma's. Ook kun je aan het einde van een program- ma op dezelfde recorder onmiddellijk beginnen met het opnemen van een nieuw programma. Opgave 4. Een oplopende rij. Inleiding. In het spelletje Rack-O krijgen de deelnemers 10 kaartjes met getallen erop. In totaal zijn er 50 kaartjes, met daarop de getallen 1 tot en met 50. De kaartjes die ze krijgen staan voor ze in een rekje; ze staan daarin van voor naar achter in de volgorde waarin de deelnemers ze hebben gekregen. Als de deelnemers aan de beurt zijn trekken ze van de stapel een nieuw kaartje; dat kaartje moeten ze in het rekje plaatsen, waarbij ze ‚‚n van de kaartjes die ze al hadden wegleggen om ruimte te maken. Wanneer een speler de getallen op de kaartjes in oplopende volgorde heeft staan is het spel afgelo- pen. Opgave. Schrijf een computerprogramma dat aan een dergelijk spelletje Rack-O kan meedoen. Eerst leest het programma tien keer een regel met daarop telkens het getal van het kaartje dat in het rekje moet worden gezet. Daarna komt op de volgende regel te staan het woord: "Spelbegin". Vervolgens geeft het programma telkens de tien getallen aan in de volgorde waarin ze op het rekje staan; gevolgd door de melding "Klaar" wanneer de kaartjes in oplo- pende volgorde staan, of door de melding "Geef:", waarna het programma een getal inleest. In dat laatste geval wordt op de volgende regel begonnen met de melding "Weg: ", gevolgd door het getal op het kaartje dat op de stapel wordt gelegd. Zie voor een voorbeeld figuur 1. Voorbeeld opgave 4. 12 17 21 3 44 32 11 19 28 40 Spelbegin 12 17 21 3 44 32 11 19 28 40 Geef: 23 Weg: 3 12 17 21 23 44 32 11 19 28 40 Geef: 37 Weg: 28 12 17 21 23 44 32 11 19 37 40 Geef: 26 Weg: 44 12 17 21 23 26 32 11 19 37 40 Geef: 34 Weg: 11 12 17 21 23 26 32 34 19 37 40 Geef: 2 Weg: 12 2 17 21 23 26 32 34 19 37 40 Geef: 18 Weg: 21 2 17 18 23 26 32 34 19 37 40 Geef: 38 Weg: 37 2 17 18 23 26 32 34 19 38 40 Geef: 35 Weg: 19 2 17 18 23 26 32 34 35 38 40 Klaar