Diákolimpiai válogató 1999


Azonosító kód  - 1. feladat (30 pont) /tesztadatok/
A processzorgyártó cégek megállapodtak abban, hogy milyen rendszert alkalmaznak az általuk gyártott processzorok azonosítására. Minden cég kap egy betűkészletet, és ezekből kell az azonosító kódot képeznie, úgy, hogy minden betű meghatározott számszor szerepeljen az azonosítóban. Például egy cég azt kapta, hogy minden azonosítója pontosan 3 db ’a’ betűt, 2 db ’b’ betűt és 1 db ’c’ betűt tartalmazhat.

Feladat:

Készíts programot (KOD.PAS vagy KOD.C), amely adott kódra meghatározza a lexikografikus (ábécé szerinti) sorrendben rákövetkező szabályos kódot, ha van rákövetkező!
Bemenet:
A KOD.BE állomány első sorában a kódok száma (1<=N<=100) van. A további N sorban az egyes kódok találhatók. Minden kód legfeljebb 100 betűből állhat, csak az angol ábécé kis betűit tartalmazhatja.
Kimenet:
A KOD.KI állományba N sort kell írni! Az i-edik sorba a bemeneti állomány i+1-edik sorában lévő kód rákövetkezőjét kell írni, ha nincs rákövetkezője, akkor a NINCS szót.
Példa:
 
KOD.BE KOD.KI
2
abaacb
cbbaaa		 ababac
NINCS

Kirakó - 2. feladat (40 pont) /tesztadatok/
Egy szókirakó játékban a játékmező (egy négyzethálós téglalap) egyes négyzeteibe kell szavakat elhelyezni vízszintesen vagy függőlegesen. A szavak egymást keresztezhetik, ekkor természetesen a közös mezőben mindkét szóban azonos betűnek kell állnia! A játékban a szavakat csak a megadott sorrendben szabad lerakni, s minden lépésben úgy kell eljárni, hogy addig az átfedő betűk száma a lehető legnagyobb legyen! Feltehető, hogy minden újabb szónak legalább 1 átfedő betűje van a már letett szavakkal.

Feladat:

Készíts programot (KIRAKO.PAS vagy KIRAKO.C), amely megadja azt a szóelhelyezést, amelyben kirakás közben és a kirakás végén is a legtöbb átfedő betű található!
Bemenet:
A KIRAKO.BE állomány első sorában a kirakandó szavak száma (2<=DB<=15) és a játékmező mérete (1<=N sor, M oszlop<=30), a második sorban pedig az első szó kezdőpozíciója (1<=OSZLOP<=M ,1<=SOR<=N) és iránya (V vagy F – jelentése vízszintesen, illetve függőlegesen) szerepel egy-egy szóközzel elválasztva. A további DB sorban az egyes értelmes magyar szavak találhatók (legfeljebb 10 karakteresek, ugyanaz a betű legfeljebb négyszer fordul elő bennük.).
Kimenet:
A KIRAKO.KI állományba DB-1 sort kell írni, a KIRAKO.BE állomány második sorának megfelelő módon, azaz egyes szavak kezdőpozícióját és irányát, egy-egy szóközzel elválasztva.
Példa:
 
KIRAKO.BE KIRAKO.KI
3 10 10
5 5 V
FA
KAP
PER		 6 4 F
6 6 V
1
 2 3 4 5 6 7 8 9 10
1
                    
2
                    
3
                    
4
          
K
        
5
        
F
A
        
6
          
P
E
R
    
7
                    
8
                    
9
                    
10
                    

Bányászrobot - 3. feladat (30 pont) /tesztadatok/
Egy robotot helyezünk egy labirintusba, megjelölve a kezdő- és a célpozícióját. A robot el kell vezetni a célig, feltéve, hogy minden lépés 1 időegységbe kerül. A robot a labirintus járatain közlekedhet vízszintes vagy függőleges irányban a 4 szomszéd hely valamelyikére lépve, valamint képes a labirintus falait is kibontani. Egy egységnyi fal kibontása a robotnak F időegységbe kerül.

Feladat:

Készíts programot (BANYASZ.PAS vagy BANYASZ.C), amely megadja, hogy minimum mennyi idő múlva érhet a robot a kezdőpozícióból a célpozícióba!
Bemenet:
A BANYASZ.BE állomány első sorában a négyzetrács magassága és szélessége (1<=N,M<=100), valamint a fal kibontásához szükséges idő (1<=F<=100) van, egy-egy szóközzel elválasztva. A következő N sor mindegyike pontosan M karaktert tartalmaz, az üres helyeken szóközt, a foglalt helyeken *-ot, a robot kezdőpozícióján K betűt, célpozícióján pedig C betűt.
Kimenet:
A BANYASZ.KI állományba egyetlen sort kell írni, azt a minimális időtartamot, ami alatt a robot a kezdőhelyről a célpozícióba érhet.
Példa:
 
BANYASZ.BE BANYASZ.KI
4 6 5
******
*K   *
******
*  C**		 8

Bírálók - 4. feladat (30 pont) /tesztadatok/
N könyvet 2 bírálónak (A és B) adnak ki, hogy mindegyikről bírálatot készítsenek. Az i. könyv elolvasása az A bírálónak Ai, a B bírálónak pedig Bi ideig tart. A két bíráló egyszerre ugyanazt a könyvet nem olvashatja, és egyszerre mindegyikük legfeljebb 1 könyvet olvashat. Egy könyv olvasását bármelyikük abbahagyhatja, s egy későbbi időpontban onnan folytathatja. A könyvek között az első K fontos könyv. Ezekre teljesülni kell, hogy bármelyik csak akkor olvasható, ha mindkét bíráló elolvasta már az összes, nála kisebb sorszámú könyvet.

Feladat:

Készíts programot (BIRALO.PAS vagy BIRALO.C), amely megadja, hogy a két bíráló mikor végezhet a lehető leghamarabb!
Bemenet:
A BIRALO.BE állomány első sorában a könyvek száma (1<=N<=1000) és a fontos könyvek száma (1<=K<=N) van. A következő N sor A és B számára az egyes könyvek elolvasásához szükséges időt tartalmazza, egy szóközzel elválasztva (1<=Ai, Bi<=100).
Kimenet:
A BIRALO.KI állományba azt az időtartamot kell írni, ami alatt a két bíráló a leghamarabb végezhet.
Példa:
 
BIRALO.BE BIRALO.KI
3 2
5 5
4 1
3 4		 15

Barátok - 5. feladat (30 pont) /tesztadatok/
Egy osztályba N tanuló jár. Mindenkinek vannak barátai. Egyikük születésnapjára kap egy könyvet, amelyről úgy gondolja, hogy mindenkinek el kellene olvasnia. Ezért egy N elemű láncot kell szervezni, ahol mindenki a barátai közül valakinek adja tovább a könyvet, amely a végén visszajut a tulajdonosához.

Feladat:

Készíts programot (BARAT.PAS vagy BARAT.C), amely megadja a láncot!
Bemenet:
A BARAT.BE állomány első sorában a tanulók száma és a barátok minimális száma (1<=N<=100, 2/3*N<=K<N) van egy-egy szóközzel elválasztva. A következő N sor mindegyike legalább K számot tartalmaz, egy-egy szóközzel elválasztva, az egyes tanulók barátainak sorszámát.
Kimenet:
A BARAT.KI állomány első sorába a lánc tagjait kell írni, feltéve, hogy az 1-es sor-számútól indult el a könyv, egy-egy szóközzel elválasztva.
Példa:
 
BARAT.BE BARAT.KI
5 3
3 4 5
4 3 5
1 2 4 5
1 3 2
1 2 3		 1 5 3 2 4

Játék - 6. feladat (40 pont) /tesztadatok/
Tekintsük azt a kétszemélyes játékot, amelyet egy NxN-es négyzethálós táblán lehet játszani. A tábla bizonyos mezőin pozitív egész számok vannak elhelyezve. A két játékos egyetlen bábut mozgat felváltva lépkedve. Egy lépésben egyet lehet lépni a bábuval szomszédos mezőre vagy lefelé, vagy jobbra. A játék akkor ér véget, amikor a második játékos a tábla jobb alsó mezőjére lép. A bábu a játék kezdetén a tábla bal felső sarkában van. Az első játékos megszerzi mindazon pontokat, amelyek olyan mezőn vannak, amire lépett. A játék célja az, hogy az első játékos, aki a játékot kezdi, a lehető legtöbb összpontot szerezze meg. A második játékos arra törekszik, hogy lépéseivel akadályozza az első játékost a legjobb eredmény elérésében.

Feladat:

Írj programot (JATEK.PAS vagy JATEK.C), amely az első játékos játékát valósítja meg. A második játékos játékát a GEP.TPU modul valósítja meg.
A játékot azzal kell kezdeni, hogy az első játékos végrehajtja a Kezd eljárást. Az első játékos saját lépését a Lep(L) eljárás végrehajtásával közli a második játékossal, ahol L értéke 'L' vagy 'J', attól függően, hogy milyen irányba lép. A második játékos válaszlépését a GepLep(L) eljárással kérdezheti le, az L Char típusú változóban kapja meg a választ, aminek értéke szintén 'L' vagy 'J' lehet, az 'L' azt jelenti, hogy a második játékos lefelé, a 'J' pedig, hogy jobbra lépett. (A GepLep eljárás mindig a második játékos utoljára végrehajtott lépését adja.).
Bemenet:
A JATEK.BE szöveges állomány első sorában két szám van: N M egy szóközzel elválasztva, N a táblamérete (1<N<=100). A következő M sorban található a kezdeti táblaállás, megadva azokat a mezőket, amelyek tartalma nem 0. Ezek három számot tartalmaznak: i j k, ami azt jelenti, hogy az i-edik sor j-edik oszlopában a táblán a k szám van. (A sorokat fentről-lefelé, az oszlopokat balról-jobbra sorszámozzuk.)
Kimenet:
A program nem írhat kimeneti állományba. A játék végeredményét a GEP modul feljegyzi.
Példa:
 
A program az alábbi szerkezetű lehet:

Program jatek;
uses gep;
begin {program}
  Kezd;
  while ... do
  begin
    ...
    Lep(L1);
    ...
    GepLep(L2);
    ...
  end;
end. {program}
 

Képtár - 7. feladat (30 pont) /tesztadatok/
A piripócsi kastély termeiben egy képkiállítást rendeztek be. N terem falain helyeztek el képeket. Egy bejárási útvonalat kell tervezni, amely az 1. teremből indul és az összes termen végighalad úgy, hogy a látogatók az összes képet pontosan egyszer láthassák, majd az 1. teremben ér véget. Ha egy teremből egy szomszéd terembe átmegyünk, akkor csak a jobb oldalon, a bejárat és a kijárat közötti falon levő képeket látja a látogató.

Feladat:

Készíts programot (KEPTAR.PAS vagy KEPTAR.C), amely az 1. teremből kiindulva megadja a bejárási útvonalat!
Bemenet:
A KEPTAR.BE állomány első sorában a termek száma (1<=N<=1000) van. A következő N sor az egyes termekkel szomszédos termek sorszámát tartalmazza (legalább 1, legfeljebb 20), az óramutató járásával ellentétes sorrendben. Minden sorban annyi szám van, egy-egy szóközzel elválasztva, ahány teremmel szomszédos az illető terem.
Kimenet:
A KEPTAR.KI állományba egyetlen sort kell írni, a bejárás sorrendjében a bejárás során érintett termek sorszámát.
Példa:
 
KEPTAR.BE KEPTAR.KI
5
2 3 4 5
1 3
1 4 2
1 3
1		 1 2 3 4 3 2 1 5 1

Autó - 8. feladat (40 pont) /tesztadatok/
Egy autót helyezünk egy labirintusba, megjelölve a kezdő- és a célpozícióját. Az autót el kell vezetni a célig, feltéve, hogy sebessége legfeljebb K lehet, s minden lépés után a sebessége 1-gyel változhat. Az autó egy időegység alatt csak vízszintesen vagy csak függőlegesen mozoghat, az S sebességű autó pontosan S távolságra lép. Az autó a kezdőpozícióban 0 sebességű (a lépése előtt 1 sebességűre vált) és a végpozícióba érve 1 sebességűnek kell lennie.

Feladat:

Készíts programot (AUTO.PAS vagy AUTO.C), amely megadja, hogy minimum mennyi idő múlva érhet az autó a kezdőpozícióból a célpozícióba!
Bemenet:
Az AUTO.BE állomány első sorában a négyzetrács magassága és szélessége (1<=N, M<=100), valamint az autók maximális sebessége (1<=K<=10) van, egy-egy szóközzel el-választva. A következő N sor mindegyike pontosan M karaktert tartalmaz, az üres helyeken szóközt, a foglalt helyeken *-ot, az autó kezdőpozícióján K betűt, célpozícióján pedig C betűt.
Kimenet:
Az AUTO.KI állományba egyetlen sort kell írni, azt a minimális időtartamot, ami alatt az autó a kezdőhelyről a célpozícióba érhet. Ha az autó nem érhet el a célpozícióba, akkor az állományba -1-et kell írni.
Példa:
 
AUTO.BE AUTO.KI
5 10 3
**********
*K       *
****** ***
C 
***   ****		 7

Minta - 9. feladat (30 pont) /tesztadatok/
Szövegelemzés során gyakran kíváncsiak bizonyos szókapcsolatok előfordulására. Erre példa ez a feladat is. Adott az S szöveg, továbbá két, A és B szó. Azt szeretnénk megtudni, hogy az S szövegben hány olyan szó van, amely AWB alakú, ahol W tetszőleges (esetleg üres) szó.

Feladat:

Írj programot (MINTA.PAS vagy MINTA.C), amely meghatározza, hogy az S szövegben hányszor fordul elő AWB alakú szó, továbbá meghatározza a leghosszabb ilyen szó előfordulásának kezdő pozícióját és hosszát.
Bemenet:
A MINTA.BE szöveges állomány két sort tartalmaz. Az első sorban az A, a másodikban a B szó található. A szavak legfeljebb 100 karakterből állnak.
A SZOVEG.BE szöveges állomány egyetlen sorában van a szöveg, amelyben keresni kell. Az A és B szavak, valamint a szöveg csak az angol ábécé kis betűit tartalmazhatják. A SZOVEG.BE állományban legfeljebb 1000000 karakter van.
Kimenet:
A MINTA.KI szöveges állomány első sorába a szövegben található AWB alakú szavak számát kell írni, ha nincs ilyen, akkor 0-át. Ha az első sor tartalma nem 0, akkor a második sor két számot tartalmazzon, a leghosszabb AWB alakú szó előfordulásának kezdő pozícióját és a szó hosszát.
A minták előfordulásainak számításakor megengedett az átfedés is. A szöveg első betűjének pozíciója 1.
Példa:
 
MINTA.BE SZOVEG.BE MINTA.KI
ab
ba		 xyaabababaaabaab 6
4 11

Vasút - 10. feladat (50 pont) /tesztadatok/
Veremsor város vasútállomásán nagy gondot okoz a szerelvények rendezése. Az állomásról továbbítandó szerelvényeket úgy kell kialakítani, hogy amikor az megérkezik a célállomásra, a szerelvény végéről mindig lekapcsolható legyen az oda továbbított kocsisor. Minden továbbítandó szerelvény négy állomást érint, ezért a rendezés előtt minden kocsit megjelölnek az 1, 2, 3 vagy 4 számokkal. A szerelvény kocsijait rendezzük át úgy, hogy a szerelvény elején legyenek az 1-essel, aztán a 2-essel, majd a 3-assal, végül a 4-essel megjelöltek. Kezdetben a kocsik az ábrán látható E-F pályaszakaszon vannak.
A vasúti váltók működése csak a következő műveleteket teszi lehetővé. Az átrendezendő kocsisorból balról az első kocsit át lehet mozgatni vagy a B-E szakaszba a már ott lévő kocsik mögé, vagy a C-D szakaszba a már ott lévő kocsik elé. A B-E szakaszban lévő első kocsi átmozdítható és hozzáilleszthető az A-B szakaszon kialakítandó kocsisor végére. Hasonlóan, a C-D szakasz első (tehát az utolsónak oda érkezett) kocsija átmozdítható és hozzáilleszthető az A-B szakaszon kialakítandó kocsisor végére.

Feladat:

Írj programot (VASUT.PAS vagy VASUT.C), amely eldönti, hogy a kívánt kocsisorrend kialakítható-e az alkalmazható műveletekkel.
Bemenet:
A VASUT.BE állomány első sora a kocsik (4<=N<=2000) számát tartalmazza. A második sorban a rendezendő szerelvények száma áll (1<=M<=100). A következő M sor mindegyike egy átrendezendő szerelvényt ír le , N db 1 és 4 közötti egész számot tartalmaz egy-egy szóközzel elválasztva.
Kimenet:
A VASUT.KI állomány M sort tartalmaz, soronként az IGEN vagy NEM szöveget, annak megfelelően, hogy a kívánt kocsisorrend kialakítható-e a megfelelő bemeneti kocsisorrendből.
Példa:
 
VASUT.BE VASUT.KI
8
3
4 4 1 2 3 4 2 3
4 3 2 1 4 3 2 1
4 1 2 3 1 2 3 4		 IGEN
NEM
IGEN

Számjegyzár - 11. feladat (50 pont) /tesztadatok/
Egy cég számjegyzárakat gyárt, ami olyan eszköz, amelynek tíz gombja van az egyes számjegyek beütésére, van egy gombja (reset), amelyet megnyomva a zár alapállapotba kerül, továbbá van egy gomb (a nyitó gomb), amelyet megnyomva a zár kinyit, feltéve, hogy az egyetlen helyes jelszót billentyűztük be. Adott jelszóra egy adott chipet gyártanak, amely véges automataként működik, és ezt építik be a zárba. Ez azt jelenti, hogy ha a jelszó N számjegyből áll, akkor az automatának pontosan N+2 állapota van. Ha az automata egy a állapotban van és egy x jelet kap (az x számjegy gombját megnyomjuk), akkor a és x által egyértelműen maghatározott b állapotba kerül. Például, ha a jelszó az 1981, akkor a hibátlanul működő automatának az ábrán látható módon kell állapotot váltania a jelek hatására, továbbá csak az a4 állapotba kerülve szabad nyitnia. Az ábrán xi az összes olyan számjegyet jelöli, amely nem i, x pedig az összes számjegyet.

Feladat:

Teszteljük a kész chipet (TESZT.PAS vagy TESZT.C), hogy jól működik-e? Csak azt tudjuk ellenőrizni, hogy jelek hatására nyitó állapotba kerül-e. Tudjuk, hogy a jelszóra a zár biztosan nyit.
A teszteléshez három művelet áll rendelkezésre, amelyeket a ZAR modul valósít meg (ZAR.TPU):
ResetA: az automatát a kezdő állapotba állítja,
Be(x:Char): az adott állapotból az automata az x ('0'<=x<='9') jel által meghatározott állapotba megy át,
Nyito:Char: Ha az aktuális állapot nyitó, akkor a visszaadott érték 'I', egyébként 'N'.
Bemenet:
A TESZT.BE szöveges állomány első és egyetlen sora tartalmazza a jelszót, ami egy legfeljebb 100 decimális jelet ('0'..'9') tartalmazó karaktersorozat, amit sorvége zár. Ha a jelszó hossza N, akkor tudjuk, hogy az automatának pontosan N+2 állapota van.
Kimenet:
A TESZT.KI állományba egy sort kell írni. Ha a számjegyzár csak a bemenetben megadott jelszóra nyit, akkor a HIBATLAN szöveget kell írni. Ha a bemenetben meg-adott jelszón kívül még más kulcsra is nyit, akkor kimeneti állományba egy olyan jelsorozatot kell írni, amelyre szintén nyit a számjegyzár.