Inhoud:

Inleiding Blz. 1

Een voorbeeldprogramma met in- en uitvoerbestanden Blz. 2

Opgave. Pentomino’s Blz. 4

Inleiding

Je krijgt vandaag een opgave met een aantal onderdelen. Bestudeer die goed, en probeer zoveel mogelijk deelprogramma’s te maken. Waarschijnlijk zal niemand alle onderdelen af kunnen krijgen binnen de tijd! Je kunt de rest van de opgaven gebruiken om thuis te oefenen. Na afloop krijg je een juryprogramma mee waarmee je kunt kijken hoeveel je op deze opgave gescoord zou hebben.

Over veertien dagen krijg je twee opgaven, vergelijkbaar opgebouwd.

De uitslag van de tweede ronde kun je ook niet vergelijken met die van een proefwerk of examen. Het is een selectieronde, waaruit maar weinig deelnemers zich kunnen plaatsen voor het vervolg.

Opdracht

Je krijgt een opdracht die uit meerdere delen is opgebouwd. Voor alle delen kun je punten verzamelen. Als je voor een deelopdracht niet snel een oplossing weet kun je deze altijd overslaan en met de volgende verder gaan. Alle deelopdrachten worden namelijk apart beoordeeld.

Let op dat je je precies aan de instructies in de opdracht houdt. Als er staat dat je twee regels met op elke regel een getal moet uitvoeren, moet je dit ook precies doen. Eén regel wordt fout gerekend; drie regels wordt ook fout gerekend.

Je programma

De programma's die je schrijft moet je inleveren onder de aangegeven naam. De extensie is afhankelijk van de programmeertaal die je gebruikt:

.BAS Basic bestand

.PAS Pascal bestand.

CPP C++ programma

.C C programma

Je moet van je programma ook een gecompileerde versie (.EXE bestand) inleveren. Dit is het programma dat gejureerd zal worden. Let er op dat je altijd je laatste versie compileert!

In- en uitvoer

Alle programma's die je schrijft krijgen hun invoer uit een tekstbestand. De invoer zal altijd goede invoer zijn die voldoet aan de beschrijving van de opdracht. Je hoeft niet te controleren op correctheid van de invoer, behalve wanneer dat in de opdracht gevraagd wordt. Let op dat je programma leest uit het bestand dat in de opgave genoemd wordt!

Je programma moet de uitvoer naar een tekstbestand schrijven. Eventuele uitvoer naar het scherm wordt niet beoordeeld. Let op dat het programma de oplossing schrijft naar het bestand dat in de opgave genoemd wordt!

Je programma mag niet wachten op invoer van het toetsenbord. Tijdens het jureren wordt geen invoer gegeven. Een programma dat oneindig lang blijft wachten op invoer van het toetsenbord zal dus 0 punten halen.

De unit CRT in Turbopascal

Gebruik van de unit crt in Turbopascal levert op snelle computers vaak een foutmelding (division by zero). Je hebt deze unit voor geen van de te schrijven programma’s nodig. Liever niet gebruiken dus!

Testen

Voor iedere opgave zijn testbestanden met voorbeeld invoer beschikbaar. De naam van het testbestand staat bij de opgave gegeven. In de deelopgaven staat ook aangegeven hoe de uitvoer er uit zou moeten/kunnen zien.

Er is een testprogramma aanwezig dat je kunt gebruiken om je programma op te starten. Dit programma zorgt ervoor dat je programma de goede invoer krijgt. Let op dat dit programma niet controleert of de uitvoer ook correct is.

Inleveren

Bij de wedstrijd moet je je programma inleveren op twee identieke diskettes. Op de diskette moet zowel de broncode van je programma staan, als het gecompileerde .EXE bestand. Op het etiket van de diskettes moet je je naam, adres en eventueel inlognummer schrijven. Op de derde diskette die je krijgt mag je je werk mee naar huis nemen.

Jurering

De jurering vindt automatisch plaats op een Pentium II-266. Bij elke opgave wordt een tijdslimiet gehanteerd. Hierbij wordt ook van deze Pentium II-266 uitgegaan. Als je programma meer tijd nodig heeft dan de tijdslimiet krijg je geen punten voor de uitgevoerde test.

Het gewicht van een vrachtwagen wordt bepaald door de lengte van de gegeven tekst. Alle vrachtwagens verschillen van elkaar in gewicht.

Op de eerste regel van het bestand OUTPUT.TXT moet je programma het gewicht van de lichtste en het gewicht van de zwaarste vrachtwagen schrijven. Op de volgende n regels moet het de ingevoerde teksten schrijven in volgorde van oplopend gewicht, één tekst per regel.

Een voorbeeld van in- en uitvoer:

Hieronder zie je in elk van de drie talen hoe je in een programma invoer kunt inlezen uit een bestand INPUT.TXT en uitvoer kunt wegschrijven naar een bestand OUTPUT.TXT

Programma in Turbo Pascal:

var inp, out: text;

n, i, wl, wh: integer;

s: array[1..10] of string[20];

begin

assign(inp,'INPUT.TXT'); reset(inp);

assign(out,'OUTPUT.TXT'); rewrite(out);

readln(inp,n);

for i:=1 to n do readln(inp,s[i]);

...

writeln(out,wl,' ',wh);

for i:=1 to n do writeln(out,s[i]);

close(out)

end.

Programma in Turbo C++:

#include <fstream.h>

ifstream inp ("INPUT.TXT");

ofstream out ("OUTPUT.TXT");

int n, i, wl, wh;

char s[11][21];

int main()

{ inp >> n;

for (i=1; i<=n; ++i) in >> s[i];

...

out << wl << ' ' << wh << '\n';

for (i=1; i<=n; ++i) out << s[i] << '\n';

return 0;

}

Programma in QuickBasic:

OPEN "INPUT.TXT" FOR INPUT AS #1

OPEN "OUTPUT.TXT" FOR OUTPUT AS #3

DEFINT A-Z

DIM s(1 TO 10) AS STRING

INPUT #1, n

FOR i=1 TO n

INPUT #1, s

NEXT i

...

PRINT #3, wl; wh

FOR i=1 TO n

PRINT #3, s

NEXT i

END

Neem vijf even grote vierkantjes en pas deze op alle mogelijke manieren aan elkaar. Je krijgt zo 12 verschillende vormen; deze vormen heten "Pentomino’s". Als je twee vormen hebt die je door schuiven, draaien en/of spiegelen precies op elkaar kunt laten vallen noemen we het hier dus dezelfde vorm!

Om de twaalf vormen uit elkaar te kunnen houden duiden we ze allemaal aan met een hoofdletter, waarvan de vorm min of meer lijkt op de betreffende pentomino. Zie onderstaande figuur uit het tijdschrift Pythagoras van februari 2000, waarin allerlei puzzels met pentomino's worden geformuleerd.

In deze opgave gaan we ze leggen op een spelbord van acht bij acht vierkantjes (uiteraard houd je dan in ieder geval vier lege vierkantjes over).

Zo stelde Solomon W. Golomb in het midden van de jaren vijftig een spel voor waarbij spelers om beurten een pentomino op zo’n bord konden plaatsen op de hokjes, zonder uit te steken of te overlappen. Degene die niet meer in staat is om te zetten verliest. Martin Gardner populariseerde het spel (1959) en vanaf het begin van de jaren zeventig is er gezocht of er met een computerprogramma een beste strategie kon worden gevonden. In 1996 verscheen een artikel waarin Hilarie K. Orman enkele winnende en verliezende eerste zetten beschreef.

Ook in bordvorm is het spel beschikbaar, onder meer onder de naam Katamino, uitgegeven door DJ Games uit Frankrijk.

Invoer.

Als invoer krijgt je programma een tekstbestand BORD.IN; dat bestand bestaat uit acht regels van elk acht hoofdletters. De letters geven aan of een hokje van het spelbord bedekt is met een pentomino; als dat het geval is wordt de bijbehorende letter aangegeven, anders staat er een O.

Voorbeeld: Bestand BORD0.IN

IIIIIOOO

UUUOOOOO

UOUOOOOO

OOVVVOOO

OOVOOOOO

OOVOOOOO

NNNOOOOO

OONNOOOO

Het spelbord van het voorbeeld.

Voorbeeldbestanden en testen:

Er zijn bestanden BORD0.IN, BORD1.IN tot en met BORD5.IN beschikbaar waarmee je je programma kunt uitproberen.

Er is een batchfile TEST.BAT, die je kunt gebruiken op de volgende manier:

TEST NIOA BORD0.IN

Met deze opdracht test je het programma NIOA (of op deze plaats één van je andere programma's), waarbij vooraf eerst de invoer uit BORD0.IN (of op deze plaats één van de andere bestanden) naar het bestand BORD.IN wordt gekopieerd. Je zult dan zelf moeten controleren of het programma binnen de tijdlimiet stopt en de goede uitvoerfile maakt.

Schrijf een programma NIOB dat een bestand BORD.IN als invoer krijgt; het programma geeft als uitvoer een tekstbestand B.UIT dat bestaat uit één regel. Op die regel staan de letters van de pentomino’s die nog niet op het spelbord liggen, op alfabetische volgorde, zonder spaties ertussen.

Een spelbord wordt als er al pentomino's op liggen verdeeld in één of meer vrije gebieden, dat zijn aaneengesloten gebieden van onbedekte hokjes. In het voorbeeld zijn dat drie verschillende gebieden.

Schrijf een programma NIOC dat een bestand BORD.IN als invoer krijgt; het programma geeft als uitvoer een tekstbestand C.UIT dat bestaat uit één regel. Op die regel staat het aantal vrije gebieden op het spelbord aangegeven.

Uitvoer bij het gegeven voorbeeld: 3

Schrijf een programma NIOD dat een bestand BORD.IN als invoer krijgt; het programma geeft als uitvoer een tekstbestand D.UIT dat bestaat uit één regel. Op die regel staat de oppervlakte van het grootste vrije gebied op het spelbord.

De volgende onderdelen gaan over het doen van zetten. Omdat het invoeren van allerlei gegevens over de twaalf pentomino's wellicht wel erg veel tijd kost is er een bestand PENTO.IN met gegevens over deze pentomino's. In dit intermezzo wordt geschetst hoe je de gegevens hieruit kunt gebruiken.

De vakjes van het spelbord worden genummerd; linksboven begin je bij 1. Naast en onder het spelbord neem je een extra rij (grijs aangegeven in figuur 3 op de volgende bladzijde). Ten opzichte van een vakje naar rechts gaan betekent één bij het nummer van het vakje optellen; naar beneden gaan betekent er negen bij optellen.

Een regel in het bestand PENTO.IN bestaat uit een letter, gevolg door vier getallen, bijvoorbeeld:

F 1 8 9 18

Dat betekent dat je, als je een F-pentomino op het spelbord legt, vanuit het eerste vak op het spelbord (gerekend volgens de aangegeven nummering) de andere vakjes die er door worden bedekt kunt vinden door de aangegeven getallen bij de waarde van dat eerste vakje op te tellen. Deze F ligt dus op de vakjes 23, 24, 31, 32 en 41.

Als je deze F zou willen neerleggen vanaf vakje 1 zou je onder andere op vakje 9 uitkomen. Dat geeft aan dat een stuk van de pentomino buiten het spelbord valt. Zodra je een stukje hebt gevonden dat buiten het bord valt hoef je dat natuurlijk niet verder te controleren.

Het bestand PENTO.IN bestaat uit 63 regels, waarin alle vormen één, twee, vier of acht keer zijn opgenomen. Dat betekent dat je je bij de volgende opgaven geen zorgen meer hoeft te maken over het draaien en spiegelen van pentomino's, alleen nog over het schuiven ervan.

Figuur 3. Het genummerde spelbord.

Schrijf een programma NIOE dat een bestand BORD.IN als invoer krijgt; het programma geeft als uitvoer een tekstbestand E.UIT dat bestaat uit één regel. Op die regel staat het aantal mogelijke zetten dat je bij dit spelbord kunt uitvoeren. Je programma mag van het in het intermezzo genoemde bestand PENTO.IN gebruik maken.

Een aanpak om het spel tegen elkaar te spelen is het verkleinen van de vrije gebieden. In deze deelopgave zoek je naar een zet die tot gevolg heeft dat in de nieuwe stelling het grootste vrije gebied een zo klein mogelijke oppervlakte heeft.

Schrijf een programma NIOF dat een bestand BORD.IN als invoer krijgt; het programma geeft als uitvoer een tekstbestand F.UIT dat bestaat uit acht regels van acht hoofdletters. Daarin wordt het spelbord aangegeven na een zet waardoor de oppervlakte van het grootste vrije gebied minimaal wordt. Je programma mag van het in het intermezzo genoemde bestand PENTO.IN gebruik maken.

Als je geen zet meer kunt doen is je uitvoerbestand gelijk aan het invoerbestand!

IIIIIOOO

UUUOOOOO

UOUOOOOO

OOVVVZZO

OOVOOOZO

OOVOOOZZ

NNNOOOOO

OONNOOOO

Tenslotte een andere strategie. Zoek een zet die tot gevolg heeft dat de andere speler zo weinig mogelijk zetten tot zijn beschikking heeft.

Schrijf een programma NIOG dat een bestand BORD.IN als invoer krijgt; het programma geeft als uitvoer een tekstbestand G.UIT dat bestaat uit acht regels van elk acht hoofdletters. Daarin wordt het spelbord aangegeven na een zet die tot gevolg heeft dat het aantal mogelijke zetten bij dit bord zo klein mogelijk is. Je programma mag van het in het intermezzo genoemde bestand PENTO.IN gebruik maken.

IIIIIOOO

UUUOOOOO

UOUOOOLO

OOVVVOLO

OOVOOOLO

OOVOOLLO

NNNOOOOO

OONNOOOO