Opgave 2. T-drop - Informatica Olympiade

Opgave 2. T-drop
T-drop is een Tetris-achtig spelletje waarbij je zoveel mogelijk T-stukken in een rechthoekige put wilt
laten vallen en waarbij je de put zo goed mogelijk wilt opvullen. De put heeft een van tevoren
vastgestelde breedte B. In het voorbeeld is dat B=6. De put is in principe oneindig hoog. De T-stukken
zien eruit zoals in het voorbeeld. Je kan de T-stukken op vier manieren in de put laten vallen. De
letter geeft aan in welke rij het T-stuk gevallen is en het cijfer geeft de oriëntatie aan.
In het voorbeeld zie je het resultaat van het laten vallen van de reeks: A1–A2–A3–A4.
A4
A3
A2
A1
Je kan het ook “raar” opvullen. Dit is het resultaat van de reeks: E4–C3–C2–D4–C3–A4–A4.
9
8
C3
7
6
D4
5 A4
4
C2
3
C3
2 A4
1
E4
Merk op dat er in voor B=6 geen zetten mogelijk zijn voor: E1 en E3.
Opdracht 2a
Je programma moet het tekstbestand in.txt openen en daaruit de volgende gegevens inlezen. Eerst
krijg je de breedte B van de put aangeboden, vervolgens het aantal T-stukken N en tenslotte op de
volgende N regels de T-stukken.
Je programma moet naar het tekstbestand uit.txt, in volgorde, de coördinaten wegschrijven van de N
T-stukken. De coördinaat is het nummer van de rij waarin het meest links en beneden geplaatste
vierkantje van de T terecht is gekomen (zie ook het voorbeeld hieronder).
Invoervoorbeeld bestand in.txt:
6
7
E4
C3
C2
D4
C3
A4
A4
Uitvoervoorbeeld bestand uit.txt:
2
3
4
6
8
2
5
Het invoer- en uitvoervoorbeeld stelt het “rare” voorbeeld van hierboven voor.
Je programma krijgt moeilijke en makkelijk opdrachten te verwerken. Het maximum aantal T-stenen
dat je programma te verwerken krijgt is echter 1000. Voor dit onderdeel kan je maximaal 40 punten
verdienen. Je programma krijgt in totaal 10 testgevallen die elk 4 punten waard zijn.
Optimaal vullen
Bij het tweede deel van deze opdracht moet je een oplossing zien te vinden voor het zo best mogelijk
opvullen van een put. Je krijgt van tevoren een breedte B en een diepte D opgegeven. Jij moet het
maximum aantal stukken S zien te vinden dat in de put past. Bijvoorbeeld: B=6 en D=4. Een mogelijke
optimale oplossing voor dit probleem is:
4
3
2
1
Voor dit voorbeeld is de oplossing dus S=5.
Opdracht 2b:
Je krijgt via stdin een breedte B en een diepte D opgegeven.
Je programma moet naar stdout het maximum aantal T-stukken S wegschrijven dat in deze put past.
Invoervoorbeeld:
6
4
Uitvoervoorbeeld:
5
Je programma krijgt moeilijke en makkelijk opdrachten te verwerken. Voor de breedte van de put
geldt: 2≤B≤7.
Voor de diepte D van de put zijn er in drie categorieën punten te verdienen: D<10, D<20 en D<30.
Per categorie krijg je maximaal 20 punten. Je programma wordt in totaal onderworpen aan 30
testgevallen, 10 per categorie. Je programma krijgt maximaal 5 seconden rekentijd per geval.

Download Report