Oefenopgave 21 maart 1998 Tweede ronde Nederlandse Informatica Olympiade. Over bestanden en in- en uitvoer. De programma's die je schrijft moet je bewaren onder de aangegeven naam. De extensie is afhankelijk van de programmeertaal die je gebruikt: BAS voor Basic-, PAS voor Pascal- en CPP voor C-programma's. Compileer je programma's ook tot een .EXE-bestand; dat zijn de programmabestanden die de jury gaat gebruiken bij het beoordelen van je programma. Je levert je programma's over veertien dagen in op twee identieke diskettes. Die diskettes moeten zowel de programmateksten als de .EXE-bestanden bevatten. Op het etiket van beide diskettes schrijf je je naam en adres; de derde diskette die je krijgt mag je gebruiken om je werk mee te nemen. Alle programma's die je schrijft krijgen hun invoer uit ‚‚n tekstbestand. Je mag er van uitgaan dat de invoer de gedaante heeft die in de opgave wordt beschreven; controle op correctheid van de invoer is niet nodig, behalve als dat in de opgave gevraagd wordt. Je programma schrijft de uitvoer naar een tekstbestand. Je programma hoeft geen uitvoer naar het scherm te produceren; dergelijke uitvoer wordt bij het jureren genegeerd. Je programma mag niet wachten op invoer van het toetsenbord. Dergelijke invoer wordt tijdens het jureren niet gegeven; een programma dat daar wel op wacht kan dus geen punten halen! Bij iedere opgave zijn testbestanden met voorbeeldinvoer beschikbaar; de naam ervan staat bij de opgave aangegeven. Ook staat bij deze testbestanden bij de deelopgaven aangegeven hoe de uitvoer er uit zou moeten/kunnen zien. Ook zijn bij beide opgaven testprogramma's aanwezig die je kunt gebruiken om te kijken of de wijze waarop je met invoer en uitvoer omgaat klopt. Bij het jureren wordt bij iedere opgave een tijdlimiet gehanteerd (uitgaande van een Pentium 75 MHz). Bij overschrijding van de limiet krijg je geen punten voor de uitgevoerde test. Op het volgende blad zie je nog eens een voorbeeldprogramma met in- en uitvoerbe- standen in de drie te gebruiken talen. Succes!! Een voorbeeldprogramma met in- en uitvoerbestanden. Opgave: De eerste regel van het bestand INPUT.TXT bevat het aantal n aan vrachtwagens dat gesorteerd moet worden (1 ó n ó 10). Elk van de volgende n regels beschrijft een vrachtwagen door een tekst van minstens 1 en hoogstens 20 kleine letters (van 'a' tot en met 'z'). 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: INPUT.TXT OUTPUT.TXT 4 1 6 aabbcc z klm ns z klm ns aabbcc 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 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] << '\'; 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 Oefenopgave. TOWER COLORS. Deze opgave is gebaseerd op een puzzel van Jan de Geus in Euclides nr. 4, januari 1998. De volledig houten puzzel "Tower colors" bestaat uit een ondergrond met daarin een aantal pinnen (in deze opgave minstens 3, hoogstens 9). Om zo'n pin kun je maxi- maal zeven houten ringen stapelen. De pinnen en de ringen zijn gekleurd; voor het gemak worden de kleuren aangeduid met hoofdletters. Van iedere kleur zijn er vier ringen. Doel van de puzzel is het plaatsen van alle ringen van een kleur om de pin van die kleur. Daarbij geldt: Je mag in ‚‚n zet ‚‚n of twee ringen die bovenaan om dezelfde pin zitten tegelijker- tijd verplaatsen naar een andere pin. Bij verplaatsen van twee ringen tegelijkertijd blijft de bovenste van de twee ook op de nieuwe pin boven de andere ring. Als de pin waarnaar je de ringen verplaatst leeg is, moet de onderste ring dezelfde kleur hebben als de pin. Als de pin waarnaar je de ring(en) verplaatst niet leeg is, moet de onderste ring die je verplaatst dezelfde kleur hebben als de bovenste ring die al om de pin zit. Een pin kan niet meer dan zeven ringen bevatten. De ringen van een kleur worden aangegeven met een hoofdletter en een volgnum- mer; bij kleur B zijn er dus de ringen B1, B2, B3 en B4. De pin van een kleur wordt aangegeven met volgnummer 0; de pin van kleur B heet dus B0. Doel van deze opgave is het doen van onderzoek in een stelling van de puzzel; wellicht zal het daarbij lukken de puzzel voor bepaalde beginstellingen werkelijk op te lossen. Invoer: Als invoer krijgt je programma een tekstbestand TOWER.IN waarin iedere regel bestaat uit eerst de aanduiding van de pin, vervolgens de aanduidingen van de schijven op die pin van onder naar boven. Voorbeeld: Bestand TOWER0.IN R0V1B2G3Y4 Y0R1V2B3G4 G0Y1R2V3B4 B0G1Y2R3V4 V0B1G2Y3R4 (Dit bestand bevat de oorspronkelijke beginopstelling van het spel) Voorbeeldbestanden en testen: Er zijn bestanden TOWER0.IN, TOWER1.IN tot en met TOWER5.IN beschikbaar waarmee je je programma kunt uitproberen. Er is een batch-file TEST0.BAT, die je kunt gebruiken op de volgende manier: TEST0 NIOA TOWER0.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 TOWER0.IN (of ‚‚n van de andere bestanden) naar het bestand TOWER.IN wordt gekopieerd. Onderdeel A: Het aantal kleuren Schrijf een programma NIOA dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand OMVANG.UIT dat bestaat uit ‚‚n regel; op die regel staat het aantal kleuren/pinnen. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: 5 Onderdeel B: Goed geplaatste ringen Schrijf een programma NIOB dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand GELUKT.UIT, bestaande uit voor iedere pin ‚‚n regel; op die regel staat het aantal ringen van de kleur van de pin dat om die pin is geplaatst. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: 0 0 0 0 0 Onderdeel C: Geldige zetten De notatie Y4G3G4 betekent dat de ringen Y4 en G3 op de ring G4 worden gelegd. Omdat iedere ring een eigen unieke code heeft is er altijd maar ‚‚n interpretatie van zo'n zet mogelijk. Schrijf een programma NIOC dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand GELDIG.UIT met daarin op de eerste regel het aantal geldige zetten in de stelling; daarna op iedere regel ‚‚n geldige zet. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: 5 Y4G3G4 G4B3B4 B4V3V4 V4R3R4 R4Y3Y4 Onderdeel D: Vastlopen Sommige reeksen van zetten zullen er toe leiden dat je geen geldige zetten meer kunt doen, zonder dat je het gewenste resultaat bereikt hebt. Schrijf een programma NIOD dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand VAST.UIT. De zetten in dat uitvoerbe- stand leiden tot een stelling waarin geen geldige zetten meer mogelijk zijn. Op de eerste regel van het bestand staat het aantal zetten, vervolgens op iedere regel een zet. Als je programma geen serie van maximaal 12 zetten kan vinden die dit resultaat oplevert, is de uitvoer een bestand met als eerste en enige regel het getal -1. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: 10 Y4G3G4 B2V1V4 R4R0 Y3Y4 B2B4 G2B1B2 V1V4V0 R3R4 Y3Y4Y2 G2G3 Onderdeel E: Snel vastlopen Bij onderdeel D werd gevraagd naar een willekeurige serie zetten waarmee je vastloopt; bij onderdeel E gaat het om een zo kort mogelijke serie van zetten waarmee dat het geval is. Schrijf een programma NIOE dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand SNELVAST.UIT. De zetten in dat bestand leiden tot een stelling waarin geen geldige zetten meer mogelijk zijn; het is een kortste serie zetten waarbij dat het geval is. Op de eerste regel van het bestand staat het aantal zetten, vervolgens op iedere regel een zet. Als je programma geen serie van maximaal 12 zetten kan vinden die dit resultaat oplevert, is de uitvoer van je programma een bestand met als eerste en enige regel het getal -1. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: 5 Y4G3G4 B2B4 V1V4 R4R0 Y4Y3 Onderdeel F: Oplossen Natuurlijk wil je graag een serie zetten zien te vinden die de puzzel oplost. Schrijf een programma NIOF dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand KLAAR.UIT. De zetten in dat bestand leiden tot een stelling waarbij op elke pin uitsluitend ringen zijn van dezelfde kleur als de pin. Op de eerste regel van het bestand staat het aantal zetten, vervolgens op iedere regel een zet. Als je programma geen serie van maximaal 12 zetten kan vinden die dit resultaat oplevert, is de uitvoer van je programma een bestand met als eerste en enige regel het getal -1. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: -1 Invoer: Zie TOWER4.IN (zie onderaan de bladzijde) Uitvoer: 12 G2G3 B3B4B1 V3V4V2 R3Y2Y1 G1G2 B3B0 B4B3 B1B2B4 V3V1 V4V3 V2V4 R3R1 Het bestand TOWER4.IN (zie opgave F en G) R0R4R2R1V2 Y0Y4Y3Y1 G0G4G3 B0G1Y2R3V4V3B4B3 V0V1B2B1G2 Onderdeel G: Snel oplossen Natuurlijk wil je tenslotte graag een zo kort mogelijke serie zetten zien te vinden die de puzzel oplost. Schrijf een programma NIOG dat als invoer krijgt een bestand TOWER.IN; het programma geeft als uitvoer een tekstbestand SNELST.UIT. De zetten in dat bestand leiden tot een stelling waarbij op elke pin uitsluitend ringen liggen van dezelfde kleur als de pin; het is het kleinste aantal zetten waarbij dat mogelijk is. Op de eerste regel van het bestand staat het aantal zetten, vervolgens op iedere regel een zet. Als je programma geen serie van maximaal 12 zetten kan vinden die dit resultaat oplevert, is de uitvoer van je programma een bestand met als eerste en enige regel het getal -1. Voorbeeld: Invoer: Zie TOWER0.IN Uitvoer: -1 Invoer: Zie TOWER4.IN Uitvoer: 10 G2G3 B3B4B1 V3V4V2 R3Y2Y1 G1G2 B3B4B0 B1B2B3 V3V1 V4V2V3 R3R1 Oefenopgave NIO. Programma Tijdlimiet Uitvoer Aantal testen Punten per test Totaal NIOA 10 sec OMVANG.UIT 4 2 8 NIOB 10 sec GELUKT.UIT 4 3 12 NIOC 15 sec GELDIG.UIT 4 3 12 NIOD 20 sec VAST.UIT 4 4 16 NIOE 30 sec SNELVAST.UIT 4 4 16 NIOF 20 sec KLAAR.UIT 4 4 16 NIOG 30 sec SNELST.UIT 4 5 20 Na afloop van de oefentijd is er een programma beschikbaar waarmee je je uitwerkin- gen kunt testen. Mededelingen daarover ontvang je na de wedstrijd.