e
3 Olympiade in de Informatica
2012 http://www.be-oi.be
D E B ELGISCHE O LYMPIADE IN DE I NFORMATICA De Belgische Olympiade in de Informatica (be-OI) is een wedstrijd in programmeren, algoritmiek en logica, georganiseerd door de Belgische universiteiten en hogescholen waar opleidingen informatica gedoceerd worden. In 2012 vindt de derde editie plaats. De wedstrijd wordt dit jaar enkel georganiseerd voor leerlingen uit het secundair onderwijs. De beste finalisten maken kans op deelname aan de Internationale Olympiade in Informatica (IOI). De Olympiade verloopt in twee rondes: • De Halve Finale in verschillende regionale centra; • en de Finale aan de Facultés Universitaires Notre-Dame de la Paix (FUNDP) te Namen. Alle informatie over de wedstrijd is beschikbaar op de officiële website: http://www.be-oi.be.
INTERNATIONALE OLYMPIADE IN DE INFORMATICA De Internationale Olympiade in de Informatica (IOI) is een internationale informaticawedstrijd voor jongeren uit het secundair onderwijs. Elk jaar vindt ze plaats in een ander land. Vorig jaar was Thailand het gastland en kon België met een medaille terugkeren. Meer dan 80 landen zijn vertegenwoordigd en sturen een nationale ploeg. De IOI is één van de door UNESCO erkende internationale wetenschappelijke olympiades, naast de olympiades voor wiskunde, biologie, chemie, fysica, aardrijkskunde, ... België neemt opnieuw deel aan de Internationale Olympiade sinds 2010, na een éénmalige vorige deelname in 1992. De Belgische Olympiade in de Informatica heeft onder meer als doel leerlingen uit het secundair onderwijs te selecteren om deel uit te maken van de Belgische ploeg op de IOI 2012, die van 23 tot 30 september in Italië plaatsvindt. U kunt meer informatie over de IOI vinden op hun officiële website: http://www.ioinformatics.org/ en over de editie 2012 op http://www.ioi2012.org/.
2
O RGANISATIE VAN DE O LYMPIADE De halve finale vindt plaats in meerdere regionale centra in België, op woensdag 1 februari 2012 van 14u tot 17u. Elk centrum kan het onthaal van de kandidaten slechts in de lokale taal garanderen. De kandidaten mogen de proef wel afleggen in de taal die zij wensen, onafhankelijk van het gekozen centrum. De proef is volledig schriftelijk. De 11 regionale centra zijn de volgende: • • • • • • • • • • •
Universiteit Antwerpen (UA); Vrije Universiteit Brussel (VUB); Université Libre de Bruxelles (ULB); Katholieke Universiteit Leuven (KUL); Universiteit Gent (UGent); Universiteit Hasselt (UHasselt); Haute École Robert Schuman de Libramont (HERS); Université de Liège (ULg); Université catholique de Louvain (UCL); Université de Mons (UMons); Facultés Universitaires Notre-Dame de la Paix de Namur (FUNDP).
Informatie over de exacte locatie van de verschillende centra en hoe ze te bereiken zijn, bevindt zich op de officiële website. De finale worden georganiseerd aan de Facultés Universitaires Notre-Dame de la Paix (FUNDP) te Namen, op woensdag 14 maart 2012 van 14u tot 18u. De finalewedstrijd bestaat uit 2 delen: een deel op papier en een deel aan de computer. De proclamatie van de laureaten zal plaatsvinden op zaterdag 17 maart 2011. Er zijn talrijke prijzen te winnen. 3
O PLEIDINGEN Tussen de twee rondes wordt een minicursus georganiseerd voor leerlingen uit het secundair onderwijs. Deze cursus vindt plaats tijdens de krokusvakantie en duurt 2 dagen. De eerste dag is gewijd aan een introductie tot de algoritmiek en programmeren en de tweede dag zal besteed worden aan meer gevorderde oefeningen. De minicursus wordt gratis aangeboden als voorbereiding op de finale voor wie weinig of geen programmeerervaring heeft. Deelname is optioneel en gratis. Tenminste 6 laureaten van de finale zullen het aanbod krijgen om deel uit te maken van een pool waaruit de leden van het Belgisch team voor de IOI geselecteerd zullen worden. Voor hen wordt een tweede en verplichte intensievere voorbereidingscursus georganiseerd in de loop van de lente. Meer informatie over deze cursussen zal aan de deelnemers worden meegedeeld en wordt ook op de officiële website gezet.
A GENDA 1 november 2011
Lancering van de OI en begin van de inschrijvingen.
29 januari 2012
Uiterste datum om in te schrijven.
1 februari 2012
Halve Finale in regionale centra.
20–26 2012
Tweedaagse cursus Algoritmiek (optioneel) voor leerlingen uit het middelbaar onderwijs (krokusvakantie).
februari
14 maart 2012
Finale aan de FUNDP in Namen.
17 maart 2012
Proclamatie en prijsuitreiking.
lente 2012
Intensieve voorbereidingscursus voor de IOI pool (Exacte data bepaald in onderling overleg).
23–30 september 2012
23de Internationale Olympiade in de Informatica (IOI) in Sirmione, Italië (http://www.ioi2012.org/).
4
V RAGEN Tijdens de wedstrijd worden de deelnemers getest op hun kennis en vaardigheden in programmeren, algoritmiek en logica. De halve finale is volledig schriftelijk; de finale is deels schriftelijk en deels aan de computer. Hieronder staan enkele vragen die bij vorige edities zijn gebruikt. Op de website van de Olympiade zijn meer voorbeeldvragen te vinden. Voor starters is op onze website ook een introductie tot de algoritmiek, pseudo-code en programmeren te vinden. 1. Een beetje logica (niveau gemakkelijk) Welk van de volgende uitdrukkingen is equivalent met ”a en b zijn oneven” : (a % b is de rest na de gehele deling (staartdeling) van a door b.)
a % a % not not
2 = 0 or b % 2 = 0 2 = 0 and b % 2 = 0 (a % 2 = 0 or b % 2 = 0) (a % 2 = 0 and b % 2 = 0)
2. De zandlopers (niveau gemiddeld) Met behulp van twee zandlopers (één van 7 minuten en één van 4 minuten) moet je 9 minuten afmeten. Je mag de zandlopers al manipuleren voordat je de 9 minuten begint te tellen. Vind de oplossing die in totaal het minste tijd in beslag neemt. 3. Ceci n’est pas un sudoku - Dit is geen sudoku (logica, niveau gemiddeld) Je neef Kris is op bezoek geweest en hij bracht een spelletje mee in de vorm van een rooster waarbij elke vakje een cijfer bevat. Je moet vertrekken in de linkerbovenhoek van het rooster en uitkomen in de rechterbenedenhoek. Je kan je alleen verplaatsen naar rechts of naar beneden. Je begint met een score van 0. Bij elke verplaatsing wordt je huidige score door 2 gedeeld (afgerond naar beneden indien nodig), vervolgens wordt de waarde van het vakje waarnaar je verspringt aan je score toegevoegd. Het doel van het spel is de rechterbenedenhoek te bereiken met de laagst mogelijke score. Wat is de kleinst mogelijke score voor elk van de volgende roosters: 0
2
9
6
0
3
9
6
1
1
9
1
1
4
4
5
3
2
1
2
8
2
5
4
1
2
3
3
1
8
5
9
4. Te ingewikkeld! (programmeren, niveau gemiddeld) Je broer is op computerkamp geweest vorig jaar. Hij is heel fier dat hij veel heeft bijgeleerd, en vooral dat hij er in geslaagd is zijn eerste algoritme helemaal zelf te schrijven. Dat algoritme neemt twee natuurlijke getallen a en
5
b en geeft als resultaat een natuurlijk getal. Hieronder staat het algoritme, waarin de operatoren / en % respectievelijk het quotiënt en de rest van de gehele deling berekenen. Leg eerst uit wat dit algoritme doet. Stel daarna een eenvoudigere versie voor. Input : a en b, twee natuurlijke getallen Output : ? c←0 p←1 while (a 6= 0 and b 6= 0) { c ← c + p ∗ ((a % 10) + (b % 10)) p ← p ∗ 10 a ← a / 10 b ← b / 10 } return c
5. Het spel met de krijtjes (logica, niveau moeilijk) Je vriend Joachim heeft je onlangs een nieuw spel aangeleerd. Dertig krijtjes worden neergelegd op een tafel. De twee spelers nemen om de beurt één, twee of drie krijtjes van de tafel weg. De speler die het laatste krijtje neemt verliest het spel. Joachim beweert dat hij altijd zal winnen als hij het spel mag beginnen. Het volgend algoritme geeft de strategie van Joachim weer, telkens hij aan de beurt is. Input
Output
: remaining, een positief geheel getal ≤ 30, zijnde het aantal krijtjes dat nog op de tafel ligt. last, het aantal krijtjes dat de tegenstander tijdens de vorige beurt van de tafel nam, dus 1, 2 of 3 (of 0 bij de eerste beurt van het spel). Joachim is zeker om te winnen als hij slim speelt. : het aantal krijtjes dat Joachim deze beurt van de tafel moet wegnemen: 1, 2 of 3.
Welke wiskundige uitdrukking heb je nodig (bestaande uit slechts 1 instructie) om het optimale aantal krijtjes voor Joachim te berekenen ? return [...]
De halve finale is zo opgesteld dat ze geen programmeerkennis vereist. Het kunnen lezen en begrijpen van een algoritme in pseudocode is echter wel handig, daarvoor verwijzen we naar de eerder vermelde documenten op de website. De finale bevat een programmeeropdracht en dus is basiskennis van éen van de volgende talen handig: C, C++, Java, Pascal, Python, PHP. Van deelnemers aan de IOI wordt verwacht dat ze vlot kunnen werken in C, C++ of Pascal. De gratis opleidingen in de krokus- en paasvakantie dienen om hiaten in deze kennis op te vullen. 6
R EGLEMENT Art. 1. De Olympiade in de Informatica (OI) is een wedstrijd in programmeren, algoritmiek en logica, georganiseerd door Belgische universiteiten en hogescholen waar opleidingen informatica gedoceerd worden. Art. 2. De OI wordt gecoördineerd door een coördinatiecomité (CCOI) bestaande uit onderwijzend personeel van Belgische universiteiten en hogescholen. Het CCOI is verantwoordelijk voor het beheer van alle aspecten van deze competitie. Art. 3. Door hun inschrijving aanvaarden de kandidaten alle bepalingen van dit wedstrijdreglement. Art. 4. De officiële talen van de OI zijn het Nederlands en het Frans. De deelnemers moeten een taal kiezen (Frans of Nederlands) waarin ze aan de wedstrijd willen deelnemen. Art. 5. De kandidaten moeten in België verblijven en moeten ingeschreven zijn aan een middelbare school gevestigd in België tijdens het schooljaar waarin de wedstrijd plaatsvindt. De kandidaten moeten jonger zijn dan 25 jaar op de eerste mei van het jaar waarin de OI worden gehouden. Art. 6. De wedstrijd is exclusief voorbehouden aan leerlingen die ingeschreven zijn in het algemeen, technisch, kunst- of beroepsonderwijs van het officiële of vrije net. De organisatoren van de OI mogen de kandidaten verzoeken een attest van inschrijving in een school voor te leggen. Art. 7. De vragen worden door het CCOI opgesteld. De halve finale is volledig schriftelijk. De finale omvat twee soorten vragen: (a) Op het eerste soort vragen moeten de kandidaten schriftelijk antwoorden. De antwoorden mogen in pseudo-code of in één van de toegestane programmeertalen gegeven worden. (b) Op het tweede soort vragen moeten de kandidaten antwoorden door een programma te schrijven aan de computer in één van de toegestane programmeertalen. De officieel toegestane programmeertalen zijn: Java, C, C++, Pascal, Python en PHP. Art. 8. Het CCOI stelt een wedstrijdjury samen die verantwoordelijk is voor het verbeteren van de antwoorden van de kandidaten, het maken van een rangschikking van de kandidaten, en het aanduiden van de laureaten. Art. 9. De OI verloopt in twee rondes: halve finale en finale. De data van deze wedstrijden zijn door het CCOI vastgesteld en in de kalender gepubliceerd. De praktische organisatie van deze twee rondes wordt in specifieke reglementen* beschreven. Art. 10. Maximum 60 kandidaten met de beste resultaten uit de halve finale, genomen over alle regionale centra heen, zullen deelnemen aan de finale. Art. 11. De laureaten van de finale zullen prijzen krijgen. Art. 12. Minstens zes finalisten (drie Franstaligen en drie Nederlandstaligen) van de wedstrijd worden door het CCOI gekozen om deel uit te maken van een pool van leerlingen, waaruit nadien deelnemers van het Belgische nationale team voor de Internationale Olympiades in Informatica (IOI) zullen gekozen worden. De kandidaten hiervoor moeten voldoen aan de criteria van de IOI: jonger zijn dan 20 jaar zijn op 1ste juli van het jaar waarin de IOI wordt gehouden, en de Belgische nationaliteit of een geldige Belgische verblijfsvergunning hebben. Het aantal deelnemers aan de pool wordt vastgelegd door het CCOI. Art. 13. Een kandidaat die weigert deel te nemen aan de IOI pool kan door een andere finalist(e) vervangen worden. Deze beslissing wordt door het CCOI genomen. Art. 14. In alle gevallen niet voorzien in bovenstaand reglement beslist het CCOI. Tegen beslissingen van het CCOI is geen beroep mogelijk.
*Reglementen voor de Halve Finale and Finale zijn beschikbaar op de website : http://www.be-oi.be.
7
De be-OI wordt mogelijk gemaakt dankzij onze sponsors :
Met de steun van :
UCLouvain ACM Student Chapter
