PO: Informatica Olympiade

PO: Informatica Olympiade 2013-2014 Wat is de Informatica Olympiade? De Nederlandse Informatica Olympiade (NIO) is een programmeerwedstrijd voor de bovenbouw van het Voortgezet onderwijs. Het is een onderdeel van de International Olympiad in Informatics (IOI). De eerste ronde van de NIO bestaat uit 4 onderdelen A, B, C en D:

De 100 inzendingen met de meeste punten (mits deze minimaal 200 punten hebben gehaald) worden uitgenodigd voor de tweede ronde van de NIO in maart 2015 op de Technische Universiteit Twente. Om mee te doen aan de olympiade moeten je uitwerkingen zijn ingeleverd bij de NIO voor 15 januari.

De PO Als PO voor Informatica gaan we de een deel van de opgaven van de eerste ronde van de NIO maken, namelijk die van categorie A. Je bent zelf vrij om ook daadwerkelijk mee te doen aan de Olympiade met je uitwerkingen (Met het maken van de PO ben je al een eind op weg , je kunt dan zelf de opgaven van categorie B, C en D nog maken voor meer punten). Meer details over hoe je meedoet en welke voorwarden er zijn, vind je in het document van de NIO op de informaticasite (en op www.informaticaolympiade.nl). Wt helpt je natuulijk graag hiermee als je besluit mee te doen.

Inleveren en beoordeling: Je doet deze PO alleen of met zijn tweeën. ( Let op: De deelname aan de NIO zelf is individueel, dus van een duo kan maar 1 persoon deelnemen, omdat je niet 2x dezelfde code in kunt leveren. Als je toch allebei wilt deelnemen, zul je verschillende versies van je oplossingen moeten maken.) Elke volledig correcte opgave is 2 punten waard (de opgaven worden wel steeds moeilijker). Deels correcte oplossingen van een opgave leveren een deel van de 2 punten op. Je zult dus alle 5 de opgaven perfect moeten maken voor een 10. Je levert bij Wt je gemaakte Javaprogramma’s in. Daarnaast maak je een begeleidend verslagje waarin je de code uitlegt. Hiermee help je mij jouw/jullie code te begrijpen en laat je zien dat je Wt/2014

1

begrijpt wat je gedaan hebt (plagiaatcontrole). Tevens lever je een logboekje in met de bestede tijd per persoon. Dit geeft mij inzicht in jullie tijdsbesteding en kan dienen als bewijsmateriaal bij eventuele onenigheid binnen een duo. Je levert alle onderdelen van de PO in in een .zip file bij de opdracht die openstaat in de ELO. Je hoeft per groepje uiteraard maar 1 keer in te leveren.

Uiterlijke inleverdatum: Zondag 30 November om 22:00 uur

Zie de volgende bladzijden voor tips, hints en uitleg om je te helpen de opgaven te tackelen.

Wt/2014

2

Aanwijzingen bij de opgaven van de NIO 2014-2015 Hieronder volgen eerst wat algemene aanwijzingen om je programma’s geschikt te maken voor de NIO opgaven. Daarna volgen specifieke tips voor opgaven A1 t/m A5. Opgaven C1 en C2 zul je helemaal zelf moeten uitvogelen. Een ‘kaal’ Java programma We hebben al gewerkt met JavaEditor en met Greenfoot (dat is een uitbreiding van de programmeertaal Java). Javacode ken je dus al en voor de NIO kun je gewoon JavaEditor gebruiken. Voor de NIO opgaven werken we alleen niet met applets zoals we vorig jaar hebben gedaan, maar met ‘kale’ Java programma’s. Het grootste verschil is dat een ‘kaal’ javaprogramma geen grafische interface heeft (dus geen knoppen en tekstvelden etc.). Het werkt slechts op de commandline (console/DOS venster). Via dat console venster kan tekstuele invoer en uitvoer worden gedaan. ‘Kale’ Javaprogramma’s hebben dus ook geen voorgedefinieerde objecten zoals Greenfoot die heeft. Je maakt een kaal javaprogramma in JavaEditor door te kiezen voor “Bestand”->”Nieuw“->”Console”:

Een leeg console Javaprogramma bevat een klein stukje standaardcode:

Je programma bestaat slechts uit een public class (De klasse waarin je hele programma zit) en een methode: public static void main(String[] args) Deze methode wordt standaard uitgevoerd als je programma start. Hier kun je dus je eigen code toevoegen.

Wt/2014

3

Invoer lezen en schrijven Om ons Java programma geschikt te maken voor het lezen van invoer en het schrijven van uitvoer, moeten we een paar dingen aan de code wijzigen. Deze code krijg je van mij cadeau, zodat je alleen op het oplossen van de problemen zelf hoeft te focussen. Pas je code aan zodat hij er zo uitziet (let op dat je de naam van de Class niet verandert (Bij mij heet hij Olympiade_opdr1). Deze moet overeenkomen met de bestandsnaam van je programmacode!):

Er zijn een paar dingen bijgekomen/veranderd:  Op de eerste regel importeren we een Java bibliotheek die het mogelijk maakt om met invoer en uitvoer te werken  We declareren een object van de klasse BufferedReader. We hebben deze de naam “reader” gegeven. Deze reader kunnen we nu in ons programma gebruiken om regels in te lezen uit de invoer van het toetsenbord.  De main methode is uitgebreid met de code throws IOException. Dit is door Java verplicht als je met invoer en uitvoer werkt. Hiermee kunnen eventuele fouten in deze invoer en uitvoer worden afgehandeld.  In de body van de main methode hebben we als voorbeeld een stukje invoer en uitvoer gedaan.

Wt/2014

4

Als je nu je programma uitvoert (dat doe je met de groene “play” knop bovenaan weet je nog?) opent er een command venster met een knipperende cursor. Je kunt nu een regel tekst intypen gevolgd door een enter. De tekst wordt ingelezen in je programma (en opgeslagen in de String variabele s). Je ziet je invoer meteen nog een keer op het scherm verschijnen. Dat komt omdat we met System.out.println(s) de inhoud van variabele s nog een keer op het scherm afdrukken. Je programma eindigt nu meteen (en vraagt je om een toets in te drukken om het console scherm te sluiten).

Aanpak Olympiadeopdracht A1 Lees eerst goed de opdrachtomschrijving van NIO opgave A1. Maak (als je dat nog niet gedaan hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de aanwijzingen op de vorige bladzijden. Bij lastigere programmeeropgaven is het altijd belangrijk het probleem in kleine stapjes te tackelen. Test steeds elke stap voordat je naar de volgende gaat. Dan weet je zeker dat je tussendoor geen fouten maakt. Zo werk je langzaam naar de oplossing toe. Hieronder een suggestie van stappen die je naar de oplossing leiden: -

Stap 1: Lees het invoer getal. Om te testen of het gelukt is, schrijf je het gelezen getal meteen naar de uitvoer.

-

Stap 2: Converteer het invoergetal naar int en maak een loopje (while of for) die precies evenveel stappen heeft als het invoergetal aangeeft. Test dit door in elke stap van je loop een regel testuitvoer te geven. Als het goed is schrijft je programma nu precies zoveel regels als het invoergetal aangeeft.

-

Stap 3: Dit is de lastigste stap en de uitdaging van deze opgave. Je moet nu de kerstboom gaan “opbouwen”. Hier zit natuurlijk een patroon in en dat zul je moeten gebruiken. Een paar hints om je op weg te helpen: o

Wt/2014

Je hebt in stap 2 een loop gemaakt gelijk aan het aantal regels dat de kerstboom hoog is. Dit noemen we de hoofdloop. Begin elke stap van de hoofdloop met een lege String. Vul deze langzaam met het juiste aantal - en *. Hiervoor heb je nog meer kleine loops nodig (zie volgende hint). Als je een regel zo gevuld hebt, druk je hem af op het scherm en begint de volgende stap van de hoofdloop.

5

o

Om een aantal keer achter elkaar hetzelfde teken in een String te zetten kun je het volgende doen: String regel = ""; for (int i=0; i<10; i++) { regel += "x"; } Bovenstaande code heeft als resultaat dat de String regel gevuld is met “xxxxxxxxxx” (10 keer “x”)

o

-

Het aantal - en * in elke regel van de kerstboom is afhankelijk van 2 dingen:  Het invoergetal  De hoeveelste regel is dit? Gebruik deze info om de binnenste loops te maken.

Stap 4: Je hebt nu de “bovenkant” van de kerstboom gemaakt. Jehoeft nu alleen de “stam” er nog onder te plakken. Dit is nu eenvoudig, want de stam is hetzelfde als de eerste regel van de kerstboom.

Aanpak Olympiadeopdracht A2 Lees eerst goed de opdrachtomschrijving van NIO opgave A2. Maak (als je dat nog niet gedaan hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de aanwijzingen op de vorige bladzijden. -

Stap 1: lees het invoergetal. Test dit weer door het getal meteen naar de uitvoer te schrijven.

-

Stap 2: zorg dat je programma invoer blijft lezen net zolang tot er een 0 wordt ingevoerd. Daarvoor kun je onderstaande code gebruiken: // lees de eerste regel van de invoer: String invoer = reader.readLine(); //zolang de invoer niet gelijk is aan 0: while (!invoer.equals("0")) { // doe iets met de invoer ... ... // lees de volgende regel: invoer = reader.readLine(); }

Wt/2014

6

-

Stap 3: Converteer steeds het invoer getal naar een int en gebruik een if om te controleren of dit getal even of oneven is (gebruik modulo %). Druk nu steeds het woord “even” of “oneven” af op het scherm om je code te testen. Als je niet meer weet hoe de modulo (%) werkt, spiek in het Javaboek op bladzijde 65.

-

Stap 4: Je kunt nu herhaaldelijk invoer lezen en bepalen of deze even of oneven is. Het zou nu eenvoudig moeten zijn om een totaal bij te houden van de kwadraten van alle oneven invoer. Zodra je programma een 0 als invoer krijgt, kun je dit totaal op het scherm afdrukken. Test het goed en controleer steeds of je uitvoer klopt.

Aanpak Olympiadeopdracht A3 Lees eerst goed de opdrachtomschrijving van NIO opgave A3. Maak (als je dat nog niet gedaan hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de aanwijzingen op de vorige bladzijden. Deze opdracht zijn eigenlijk 4 opdrachten in een, die je los van elkaar kunt zien. Twee hiervan hebben we letterlijk gedaan bij de Javalessen in klas 5. Laten we die eerst tackelen: -

Stap 1: De eerste opdracht is het teruggeven van de lengte van de invoer. Dit is gemakkelijk te doen met 1 enkel javacommando. Check hoe je de lengte van een String opvraagt in het Javaboek pagina 70.

-

Stap 2: We slaan de tweede en derde opdracht even over, omdat we de vierde opdracht ook bijna letterlijk uit het Javaboek kunnen overnemen. Kijk op pagina 70 van het Javaboek om te kijken hoe je een String omdraait.

-

Stap 3: We gaan verder met opdracht 2, omdat deze het makkelijkst is. Je zult net als bij de vorige stap met een loop langs alle letters van de invoer moeten. Java heeft een ingebouwd commando om van een teken te kijken of het een hoofdletter is. Die kunnen we goed gebruiken: Character.isUpperCase() Deze methode heeft 1 nadeel: hij werkt op variabelen van het type char en niet op String. Een char is een Java type dat we nog niet kennen. Het bevat 1 enkel ASCII teken. Gelukkig is er ook een commando om een char uit een String te halen: String mijnString = "Ik ben een voorbeeld"; char letter = mijnString.charAt(3); In het voorbeeld bevat de variabele letter nu het teken op positie 3 uit mijnString, dus een ‘b’ (let op we beginnen te tellen bij 0, dus positie 3 is de 4e letter!)

Wt/2014

7

We zouden nu kunnen doen om te checken of het een hoofdletter is: if (Character.isUpperCase(letter)) { ... } Zorg nu dus dat je 1 voor 1 alle letters uit de invoer haalt en kijkt of het een hoofdletter is. Houd in een teller bij hoeveel hoofdletter je tegenkomt en druk deze uiteindelijk op het scherm af. -

Stap 4: Tot slot moeten we het aantal verschillende letters tellen. o

Java heeft een commando om op te vragen of een String een bepaald teken bevat. Die kunnen we goed gebruiken. Een voorbeeld om dat commando te illusteren: String mijnString = "Ik ben een voorbeeld"; if (mijnString.contains("q")) { ... } In het voorbeeld vragen we in een if of mijnString de letter q bevat.

o

Een naieve manier om dit probleem te tackelen is om van elk mogelijk teken te vragen of deze in de invoer zit en zo alle verschillende tekens te tellen. Dit is erg omslachtig en je weet niet precies welke tekens zijn toegestaan (er zijn ook namen met trema’s erin bijvoorbeeld, zoals Daniël). Dat zijn wel erg veel ifs...

o

Een slimmere manier is als volgt:  Maak een lege String aan met de naam uniekString  Doorloop letter voor letter de invoer (zoals bij stap 2)  Kijk steeds of de huidige letter van de invoer al voorkomt in uniekString. Zo nee: voeg de huidige letter toe aan uniekString.  Als je alle letters van de invoer hebt gehad, bevat uniekString alleen maar verschillende letters  Je hoeft nu alleen maar de lengte van uniekString op te vragen voor het goede antwoord.

Aanpak Olympiadeopdracht A4 Lees eerst goed de opdrachtomschrijving van NIO opgave A4. Maak (als je dat nog niet gedaan hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de aanwijzingen op de vorige bladzijden. Wt/2014

8

De invoer voor deze opdracht bestaat uit 4 regels van 4 tekens (de tekens 0 of 1). Na het accepteren van deze invoer, moet je horizontaal en verticaal gaan zoeken in deze invoer. Dat lukt je alleen als je de invoer op de juiste manier opslaat: in een array. Een tweedimensionaal array om precies te zijn. Hoe zat dat ook alweer met die arrays? Misschien is dit een goed moment om de stof daarover nog eens te bekijken. Lees Wt’s stof over arrays van vorig jaar en dan met name pagina 4 over 2D arrays. Een opmerking over deze opgave: Als je goed naar het voorbeeld kijkt dat bij de opgave staat, zie je dat grotere reeksen voor gaan op kleinere. Dat wil zeggen als op een regel staat 0111, dan is dat een reeks van 3 x 1 en niet 2 reeksen van 2 x 1. Het is dus belangrijk om per regel de grote reeksen eerst te checken. Pas als een grote reeks niet gevonden is, ga je kijken of er misschien een kleinere reeks te vinden is.Houd dit in je achterhoofd bij het stappenplan Een stappenplan om deze opgave te tackelen: -

Stap 1: Zoals gezegd zal de invoer in een 2D array moeten worden opgeslagen. Omdat elk “vakje” van de invoer uit 1 teken bestaat (0 of 1) ligt het voor de hand om een array van het type char te gebruiken: char[][] matrix = new char[4][4]; Zo creer je een 2D char array, met 4 elementen in beide richtingen. Precies groot genoeg om de 4x4 invoer in op te slaan. Gebruik een loop om de 4 regels van de invoer 1 voor 1 te accepteren en de losse tekens (gebruik .charAt() ) op te slaan op de juiste plek in het array. Om te testen of het goed is gegaan kun je het beste (met weer een loop) de inhoud van je array op het scherm afdrukken. Deze zou dan dus identiek moeten zijn aan de gegeven invoer.

-

Stap 2: Maak 6 int tellers aan die je elk op 0 initialiseert. Deze 6 tellers houden bij hoeveel reeksen van elke soort (2x0, 2x1, 3x0, 3x1, 4x0, 4x1) je tot nu toe hebt gevonden. Met slimme loops gaan we zometeen door de invoer heen. Als we een reeks vinden, verhogen we de juiste teller. Als we dan klaar zijn met de invoer bekijken, bevatten de 6 tellers het goede antwoord en kunnen we deze op het scherm afdrukken.

-

Stap 3: Begin met checken op reeksen van 4 x 0 of 4 x 1. Dit moet natuurlijk zowel horizontaal als verticaal gecheckt worden. Om horizontaal te kijken of er een reeks van 4 x 0 is. Moeten we simpelweg kijken of alle 4 de elementen van een regel gelijk zijn aan 0. Zoiets als dit:

Wt/2014

9

if (matrix[0][0]=='0' && matrix[0][1]=='0' && matrix[0][2]=='0' && matrix[0][3]=='0') { … … } Met deze voorbeeldcode checken we of de eerste horizontale rij (rij 0) uit allemaal 0en bestaat. Dit moeten we natuurlijk checken voor elk van de 4 rijen. Dit kan slim met een loop. Op een vergelijkbare manier check je de verticale kolommen. Om te testen of je het goed hebt gedaan, zou ik na het checken het aantal gevonden reeksen afdrukken. JE kunt makkelijk op het oog natellen of je antwoord (en daarmee je code) klopt. -

Stap 4: Als je een rij of kolom hebt gecheckt op een reeks van 4 en deze niet hebt gevonden, dan moet je gaan checken op een reeks van 3. Dit gaat natuurlijk vergelijkbaar met checken op een reeks van 4. Let op det er op 2 manieren een reeks van 3 kan zijn, namelijk aan het begin of aan het eind van een rij of kolom

-

Stap 5: Als je een rij of kolom hebt ook hebt gecheckt op een reeks van 3 en deze niet hebt gevonden, rest nog om te checken op reeksen van 2. Dit gaat wederom vergelijkbaar. Let op dat er op 3 manieren een reeks van 2 in een rij of kolom kan zitten. Namelijk aan het begin, in het midden en op het einde.

Verzin een paar testcases en check of je programma het goede antwoord geeft bij alle cases.

Aanpak Olympiadeopdracht A5 Lees eerst goed de opdrachtomschrijving van NIO opgave A5. Maak (als je dat nog niet gedaan hebt) een nieuw javaprogramma aan en maak deze geschikt voor in- en uitvoer volgens de aanwijzingen op de vorige bladzijden. Opgave 5 is met afstand de pittigste. Je hebt in ieder geval de volgende arrays nodig: - Een (2D) array om de uitgebrachte stemmen per deelnemer op te slaan - Een array om per stemronde te turven hoeveel stemmen elke kandidaat krijgt - Een array om bij te houden welke kandidaten nog verkiesbaar zijn (zodat je weet hoe je de stemmen moet tellen in elke ronde Al deze arrays moeten variabel van lengte zijn, omdat je van te voren niet weet hoeveel kandidaten en deelnemers er zijn. Je zult vervolgens met een slimme loop net zoveel stemrondes moeten doorlopen als nodig is om een winnaar te kiezen. Per ronde waarin geen winnaar gevonden is, moet je de verliezer af laten vallen ,zodat deze niet meer meetelt in de volgende ronde. Voor nu zijn dit alle hints. Op verzoek kan Wt de uiteg bij deze opgave nog uitbreiden.

Wt/2014

10

Nuttige links Olympiade site: http://www.informaticaolympiade.nl Uitleg over arrays: http://www.stedgymdenbosch.nl/subsites/informatica/data/veilig/Wt%20%20Arrays%20en%20sorteren.pdf Java voor beginners met goede tutorials: http://www.homeandlearn.co.uk/java/java.html Goede site om Java dingen op te zoeken: http://www.leepoint.net/notes-java/index.html Enigma Java informatieboek: http://www.sgdb.nl/subsites/informatica/data/veilig/deel1/infboek/4%20VisProg%20infboek.p df Enigma Java werkboek: http://www.sgdb.nl/subsites/informatica/data/veilig/deel1/verwboek/4%20VisProg%20verwbo ek.pdf Wt uitleg Java arrays: http://www.sgdb.nl/subsites/informatica/data/veilig/Wt%20%20Arrays%20en%20sorteren.pdf

Wt/2014

11