(klik voor opgave 1, opgave 3) opgave 2 in pdf
Let op: Willem van der Vegt, de wedstrijdleider, geeft op aparte pagina's antwoord op vragen en opmerkingen. Soms geeft hij ook verduidelijkingen en correcties.
Opgave 2. Verstop je codewoord
Onderdeel 2A
Inleiding
Bij deze opgave gaat het om het schrijven van een programma nio2 dat in staat is om van een codewoord een letterbrij van een aangegeven lengte te maken. Als dat onmogelijk is geeft het programma een foutmelding.
Letterbrij en codewoord
Een codewoord is een tekst van tenminste één en ten hoogste vijftien kleine letters zonder leestekens.
De letterbrij moet voldoen aan de eisen van opgave 1: Als je alleen elke derde keer dat een letter voorkomt in de letterbrij hem niet wegstreept, kom je op het codewoord uit.
Invoer
Invoer is een bestand nio2.in dat bestaat uit twee regels:
Op de eerste regel staat een tekst van tenminste één en ten hoogste vijftien kleine letters zonder leestekens.
Op de tweede regel staat een getal L dat aangeeft hoe lang de letterbrij die je moet maken dient te worden. Er geldt dat 1 ≤ L ≤ 150.
Uitvoer
Uitvoer is een bestand nio2.uit dat bestaat uit één regel.
Zo mogelijk is dat de gevraagde letterbrij.
Wanneer het niet mogelijk is om een letterbrij van de aangegeven grootte te maken staat er een foutmelding:
< L is te klein om bij dit codewoord een geldige letterbrij te maken
> L is te groot om bij dit codewoord een geldige letterbrij te maken.
Voorbeelden
Voorbeeldnr. |
Invoer nio2.in |
Uitvoer nio2.uit |
1 |
bal |
balbalbal |
2 |
haast |
< |
3 |
uilebal |
> |
4 |
bal |
lblabbaqalq |
5 |
droom |
rdadadroxmocpronogomocdmqzx |
Punten voor deze opgave
Voor het correct ontdekken of een letterbrij wel of niet te maken is kun je 20 punten krijgen.
Het maken van een geldige letterbrij bij het codewoord levert je 40 punten op.
Onderdeel 2B
Zoals je aan voorbeeld 1 al kunt zien is het mogelijk om een geldige letterbrij te maken die toch niet echt veel verstopt. Als je voor de extra punten van deze opgave in aanmerking wilt komen moet je programma aan de voorwaarden die hieronder worden uitgewerkt voldoen: Een zo laag mogelijke op-en-neer-score en een zo hoog mogelijke afstandsscore. Deze voorwaarden worden los van elkaar beoordeeld.
Aanvullende voorwaarde 1: Een zo laag mogelijke op-en-neer-score.
Een letterbrij doet bij voorkeur nogal willekeurig aan. Om te kijken hoe jouw letterbrij eruit ziet berekenen we de op-en-neer-score van je letterbrij.
Deze score bereken je als volgt:
Bekijk alle paren letters (l1,l2) die meteen naast elkaar voorkomen in de letterbrij en stel vast in welke categorie ze vallen:
Categorie Op: l1 < l2 (dus l1 komt voor l2 in het alfabet)
Categorie Neer: l1 > l2 (dus l1 komt na l2 in het alfabet)
Categorie Gelijk: l1 = l2
Het aantal paren in de categorie Op noem je O.
Het aantal paren in de categorie Neer noem je N.
Het aantal paren in de categorie Gelijk noem je G.
De op-en-neer-score van je letterbrij is (O-N)2+G2
Je kunt in totaal 25 punten voor deze opgave verdienen als de op-en-neer-score van je letterbrij bij de gegeven invoer minimaal is.
Er is een programma ons.exe (klik hier) beschikbaar waarmee je de op-en-neer-score van een bestand kunt bepalen. Open een commandovenster en geef als opdracht ons nio2.uit en je ziet de score op het scherm weergegeven.
Voorbeelden:
nio2.uit |
Op-en-neer-score |
balbalbal |
4 |
lblabbaqalq |
2 |
rdadadroxmocpronogomocdmqzx |
4 |
Aanvullende voorwaarde 2: Een zo hoog mogelijke afstandsscore.
Een letterbrij bevat het codewoord, maar bij voorkeur herken je dat er niet zo makkelijk in.
Op de volgende manier kun je de afstandsscore van een codewoord in een letterbrij bepalen.
Ga na welke letters niet meer dan twee keer in de letterbrij voorkomen.
Laat deze letters uit de letterbrij weg. Wat je overhoudt noemen we de goedeletterzin.
Nu ga je het codewoord vergelijken met elk van de deelzinnen van de goedeletterzin: je legt het codewoord naast de goedeletterzin, vergelijkt codewoord en deelzin en telt het aantal verschillen. Daarna schuif je het codewoord telkens één plaats op en tel je telkens opnieuw de verschillen (Zie het voorbeeld hieronder).
Voorbeeld berekening afstandsscore:
Letterbrij: lblabbaqalq
Codewoord: bal
Goedeletterzin: lblabbaal
Goedeletterzin |
Deelzin/codewoord |
Verschillen |
lblabbaal |
lbl - bal |
2 |
bla - bal |
2 |
|
lab - bal |
2 |
|
abb - bal |
2 |
|
bba - bal |
2 |
|
baa - bal |
1 |
|
aal - bal |
1 |
Het kleinste verschil noem je A.
Het aantal keren dat dit kleinste verschil voorkomt noem je N.
De afstandsscore van codewoord en letterbrij is nu 10A+1 – N.
Je kunt voor deze opgave 15 punten verdienen als de afstandsscore van de door jou gevonden letterbrij bij het gegeven codewoord maximaal is.
Er is een programma afsc.exe (klik hier) beschikbaar waarmee je de afstandsscore van een bestand kunt bepalen. Open een commandovenster en geef als opdracht afsc nio2.in nio2.uit en je ziet de score op het scherm weergegeven.
Voorbeelden:
nio2.in |
nio2.uit |
Afstandsscore |
bal |
balbalbal |
7 |
bal |
lblabbaqalq |
98 |
droom |
rdadadroxmocpronogomocdmqzx |
996 |
