Diákolimpiai válogató 2001


Pártok - 1. feladat (30 pont) /tesztadatok/
Az elmúlt 200 évben Európa 2 országában feljegyezték, hogy a választások után milyen párt (baloldali vagy jobboldali) adta a miniszterelnököt. Olyan időszakokat keresünk, amikor az összes országban ugyanolyan jellegű párt volt hatalmon. A győztes adja a miniszterelnököt a választás napjától a kővetkező választást megelőző napig.

Feladat:

Készíts programot (PARTOK.PAS vagy PARTOK.C), amely megadja azokat az időintervallumokat a legelső választás és az aktuális idő között, amikor mindegyik országban azonos jellegű párt volt hatalmon!
Bemenet:
A PARTOK.BE állomány első sorában az aktuális dátum szerepel (év, hónap, nap, egy-egy szóközzel elválasztva). A második sorban az első országbeli választások száma van (1<=N<=200), a következő N sor pedig egy-egy választás eredményét tartalmazza. Utána következik a második országbeli választások száma (1<=M<=200), majd M sorban újra egy-egy választás eredménye. A választási eredmény első karaktere a B vagy a J betű, attól függően, hogy baloldali, vagy pedig jobboldali párt adta a mrniszterelnököt, ezt követi három egész szám, egymástól és az első betűtől egy-egy szóközzel elválasztva: a választás éve, hónapja és napja.
Kimenet:
A PARTOK.KI állomány első sorába azon időintervalhimok K számát kell írni, amikor mindegyik országban azonos jellegű párt adta a miniszterelnököt, a következő K sorba pedig növekvő időrendben az egyes intervallumokat. Minden intervallum 6 egész számot tartalmaz egymástól egy-egy szóközzel elválasztva: az időszak elejét (év, hónap, nap) és végét (év, hónap, nap). Ha két egymáshoz illeszkedő intervallumban ugyanaz a párt adta mindkét országban a miniszterelnököt, akkor az egy (!) intervallumnak számít!
Példa:
 
PARTOK.BE PARTOK.KI
PARTOK. BE
2001 5 1
3
J 1990 5 4
B 1994 5 12
J 1998 5 8
4
J 1992 6 11
J 1993 6 1
B 1996 6 30
B 1998 2 15		 2
1992 6 11 1994 5 11
1996 6 30 1998 5 7

Dominó - 2. feladat (30 pont) /tesztadatok/
Dominóval sokféle játékot lehet játszani. Mohó Marci a következő kétszemélyes változatot kedveli. Minden dominó mindkét oldala legfeljebb 6 pöttyöt tartalmazhat, de Üres is lehet. A játékban csak a 28 különböző dominó használható. A játékosok először megállapodnak, hogy az adott játékot hány dominóval fogják játszani. Jelöljük ezek számát N-el. Ez után mindkét játékos kap véletlenszerűen N (különböző) dominót, úgy, hogy legalább az egyiknek lesz dupla dominója (amelynek mindkét felén ugyanannyi pötty van). Az a játékos kezdi a játékot, akinél a legnagyobb dupla dominó van, amelyet első lépéseként le is rak. Felváltva lépnek, azonban ha a soron következő játékos nem tud lépni, akkor átadja a lépés jogát az ellenfélnek. Egy lépés abból áll, hogy a játékos egy olyan saját dominóját, amely valamelyik felével illeszkedik a már lerakott dominósor bal végéhez, oda rakja.

A játék akkor ér véget, ha

Feladat:
Készíts programot (DOMINO.PAS, illetve DOMINO.C), amely meghatározza, hogy adott kezdeti játékállásra milyen kimenetele lehet a játéknak! (A feladat nem az, hogy meghatározzuk, hogy van-e és melyik játékosnak van nyerő stratégiája! Az összes lehetséges szabályos játékmenet eredménye a kérdés.)
Bemenet:
A DOMINO.BE állomány első sorában a tesztesetek T (1<=T<=10) száma van. Minden teszteset három sort tartalmaz. Az első sorban van a játékban játékosonként kapott dominók N száma (1<=N<=10). A következő két sor mindegyike pontosan 2*N egész számot tartalmaz egy-egy szóközzel elválasztva. Az első sor az első játékos (A), a második sor a második (B) játékos dominóit irja le, egy-egy számpár egy dominót ad meg.
Kimenet:
A DOMINO.KI állományba pontosan T sort kell írni, soronként a megfelelő teszteset eredményét! Az adott sor az A betűt tartalmazza, ha bárhogyan is játszanak, csak az első (A) játékos nyerhet, a B betűt, ha csak a második (B) játékos nyerhet. Az AB betűpárt (szóközök nelkül), ha mindkét játékos nyerhet, illetve a D betűt, ha egyikük sem nyerhet, bárhogy játszanak is.
Példa:
 
DOMINO.BE DOMINO.KI
4
4
3 3 3 5 3 6 4 5
1 2 1 5 4 6 5 6
4
0 1 0 3 2 2 3 3
1 5 3 5 5 5 5 6
4
3 3 3 5 3 6 4 6
0 1 0 5 3 4 4 5
6
0 3 0 5 1 4 1 5 2 5 3 3
1 1 2 6 3 6 4 4 4 6 6 6		 D
B
A
AB

Lovak - 3. feladat (40 pont) /tesztadatok/

Lótenyésztők sok generációra visszamenőleg tartják nyilván lovaik leszármazását.. A lovakat sorszámukkal azonosítjuk és vagy mindkét szülőjüket ismerjük, vagy csak az egyiket, vagy pedig egyiket sem. Így ismerhetjük a lovak nagyon régi őseit is. Előfordulhat, hogy egy ló egyes ősei többféle leszármazási ágon is ősök.

Feladat:

Készíts programot (LOVAK.PAS vagy LOVAK.C), amely adott ló esetén megadja, hogy
Bemenet:
A LOVAK.BE állomány első sorában a nyilvántartott lovak N és leszármazási kapcsolatok M száma van (1<=N, M<=1000). A következő M sor mindegyike 2 egész számot tartalmaz egy szóközzel elválasztva, az első szám egy ló sorszáma, a második pedig az egyik szülőjének sorszáma. Az utolsó sorban egy ló L sorszáma van (1<=L<=N).
Kimenet:
A LOVAK.KI állomány első sorába azon lovak számát kell írni, ahányan többszörös ősei az L lónak, a második sorba pedig azon ló sorszámát, amely a legtöbb leszármazási úton szerepel.
Példa:
 
LOVAK.BE LOVAK.KI
10 11
10 3
1 2
1 3
2 4
2 5
3 5
3 6
5 7
4 8
6 8
6 9
1		 3
3

Minta - 4. feladat (30pont) /tesztadatok/

A mintakeresés igen gyakori feladat a szövegfeldolgozásban, számtalan változatban előfordul. Tekintsük a következő változatát. Adott egy szöveg és egy minta. Azt mondjuk, hogy a szöveg tartalmazza a mintát, ha van olyan része a szövegnek, amelyből karaktereket elhagyva pontosan a mintát kapjuk.

Feladat:

Készíts programot (MINTA.PAS vagy MINTA.C), amely adott szöveg és minta bemenetre meghatározza a szövegnek egy olyan legrövidebb részét, amely tartalmazza a mintát!
Bemenet:
A MINTA.BE szöveges állomány első sora a minta M (0<M<=100) hosszát, a második sora pedig a mintát tartalmazza. A harmadik sorban a szöveg N (0<N<=10000) hossza van. A negyedik sor tartalmazza a szöveget, ami pontosan N karakterből áll.
Kimenet:
A MINTA.KI szöveges állomány első és egyetlen sorába egy i j egész számpárt kell írni egy szóközzel elválasztva. A szöveg i-től j-ig (i-t és j-t is beleértve) tartó része tartalmazza a bemenetben megadott mintát, és a szövegnek nincs olyan j-i+1 -nél rövidebb része, amely szintén tartalmazná a mintát. Ha a szövegnek nincs olyan része, ami tartalmazná a mintát, akkor a 0 0 számpárt kell kiírni! Ha több megoldás is van, akkor azt kell kiírni, amelyiknél az i érték a legkisebb!
Példa:
 
MINTA.BE MINTA.KI
5
elemi
55
amelyből karaktereket elhagyva pontosan a mintát kapjuk		 3 44

Ütemezés - 5. feladat (30pont) /tesztadatok/

Mohó Márton vállalkozó egy pályázaton meghirdetett munkák között válogat. Ismeri minden munka határidejét, és azt, hogy az adott munka elvégzése mekkora hasznot eredményez. Minden munka elvégzésére 1 napra van szüksége, és egy nap csak egy munkát tud elvégezni.

Feladat:

Készíts programot (UTEMEZ.PAS vagy UTEMEZ.C), amely kiszámítja, hogy
Bemenet:
Az UTEMEZ.BE szöveges állomány első sora a munkák N (0<N<=10000) számát tartalmazza. A további N sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva. Az első szám, H a munka határideje (0<H<10000), a második P pedig a munka elvégzésével elérhető haszon (0<P<1000). Ha egy munka hatrárideje K, az azt jelenti, hogy ha a munkát elvállaljuk, akkor azt a K-adik napig (a K. napon még lehet) be kell fejezni.
Kimenet:
Az UTEMEZ.KI szöveges állomány első sorába az elérhető legnagyobb összhaszont kell írni! A második sorba azoknak a munkáknak a sorszámait kell kiírni, amelyek elvégzése az első sorba írt összhasznot eredményezi, ha a munkákat ebben a sorrendben végzik el, azaz a sorban az i-edik munkát az i-edik napon.
Példa:
 
UTEMEZ.BE UTEMEZ.KI
6
3 60
4 40
1 10
3 30
7 70
4 20		 220
6 4 1 2 5

Térkép - 6. feladat (40pont) /tesztadatok/

Egy térképen különböző országokat ábrázolunk. Minden egyes ponthoz megadjuk, hogy melyik országhoz tartozik. (Az országokat sorszámukkal azonosítjuk, a területük összefüggő. Az országok száma legfeljebb 100.) Útnak nevezzük szomszédos helyek sorozatát, ami egyik helyről egy másikra vezet. (Mindig 4 szomszédot vizsgálunk, átlósan nem léphetünk.) Egyes országok (legfeljebb 100 pár) megállapodtak egymással, hogy a határukon semmiféle útlevélellenőrzést nem végeznek, így ott gyorsabb a határátlépés.

Feladat:

Készíts programot (TERKEP.PAS vagy TERKEP.C), amely két hely koordinátái alapján megadja, hogy
Bemenet:
A TERKEP.BE állomány első sorában a térkép sorainak N és oszlopainak M száma (l<=N, M<=100), valamint az útlevél-ellenőrzést megszüntető országpárok száma van (0<=SZ<=100). A következő N sor mindegyike M egész számot tartalmaz, egy-egy szóközzel elválasztva, annak az országnak a sorszámát, amelyhez az adott pont tartozik. A következő SZ sor mindegyike 2 számot tartalmaz, olyan országok sorszámát, ahol a határt át lehet lépni útlevél-ellenőrzés nélkül. Az utolsó sorban 4 egész szám van, a kezdő- és a célhely sor, illetve oszlopkoordinátája (1<=KSOR<=N, 1<=KOSZLOP<=M, 1<=VSOR<=N 1<=VOSZLOP<=M).
Kimenet:
A TERKEP.KI állomány első sorába azon országok számát kell írni, ahányon minimum át kell haladni, hogy a kezdőpontból a végpontba jussunk, a másodikba pedig azon útlevél-ellenőrzéses határátlépések számát, amelyeken a minimum át kell haladni!
Példa:
 
TERKEP.BE TERKEP.KI
5 6 1
1 1 1 1 1 1
1 1 2 2 1 1
1 1 2 3 3 1
1 1 2 3 3 1
1 1 2 3 1 1
1 3
1 2 5 4		 2
0

Darabolás - 7. feladat (50 pont) /tesztadatok/

Adott egy fémrúd, amelyet megadott számú és hosszúságú darabokra kell felvágni. A darabok hosszát miliméterben kifejezett értékek adják meg. Olyan vágógéppel kell a feladatot megoldani, amely egyszerre csak egy vágást tud végezni. A vágások tetszőleges sorrendben elvégezhetőek. Egy vágás költsége megegyezik annak a darabnak a hosszával, amit éppen (két darabra) vágunk. A célunk optimalizálni a műveletsor teljes költségét.

Feladat:

Készíts programot (DARABOL.PAS vagy DARABOL.C), amely
Bemenet:
A DARABOL.BE szöveges állomány első sora egy egész számot tartalmaz, a darabok N számát (0<N<=1000). A második sor N darab pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, a darabok hosszát. A második sorban szereplő számok nem nagyobbak, mint 1000.
Kimenet:
A DARABOL.KI szöveges állomány első sorába egyetlen számot, a vágási műveletsor optimális összköltségét kell írni! A további N-1 sor mindegyikébe két egész számot kell írni, egy szóközzel elválasztva. Az első szám legyen az adott lépésben kettévágott léc hossza, a második szám pedig az egyik keletkező darab hossza. Minden sor csak olyan hosszúságú darab kettévágását tartalmazhatja, amelyből a korábbi lépések során több keletkezett, mint az azóta elvégzett lépések által felhasználtak száma. Ha több vágássorozattal is el lehet érni az optimális költséget, akkor ezek közül bámelyiket meg lehet adni.
Példa:
 
DARABOL.BE DARABOL.KI
5
2 5 2 7 10		 55
26 10
16 7
9 4
4 2

Háromszög -8. feladat (50 pont) /tesztadatok/

Adott egy N oldalhosszúságú háromszög. A háromszög - az elemek elrendezését tekintve - hasonló a Pascal háromszögre, tehát minden elem fölött balra és jobbra (ha nem a háromszög bal vagy jobb oldalán helyezkedik el) található egy-egy elem.

Adott a háromszög elemeivel együtt. Ez egy játék, amit két játékos játszik. A háromszög oldalának hossza páros. Minden lépésben a soron következő játékos a háromszög három oldala közül választhat, és amelyik oldalt választja, azon oldal mentén levő elemek az ő birtokába kerülnek. Ezeket az elemeket eltávolítja a háromszögből, ezáltal egy (N-1) méretű háromszöget kapunk. Most a második játékos lép, hasonló szabály alapján.

Feladat:

Készíts programot (HAROM.PAS vagy HAROM.C), amely kiszámítja, hogy maximálisan hány pontot tud összegyűjteni az első játékos, feltéve, hogy a második játékos úgy játszik, hogy a legtöbb pontot szerezze meg. Pontszám alatt a birtokában lévő elemek összegét értjük.
Bemenet:
A HAROM.BE szöveges állomány első sora egyetlen egész számot tartalmaz, a háromszög N oldalhosszát (0<=N<=24) (N páros szám). A következő N sor tartalmazza a háromszög leírását. Az állomány i-edik sora (i-1) darab pozitív egész számot tartalmaz egy -egy szóközzel elválasztva, ami a háromszög (i-1)-edik sora lesz. Minden háromszögbeli szám értéke legfeljebb 100.
Kimenet:
A HAROM.KI szöveges állomány első sorába egyetlen számot kell írni, ami az első játékos által megszerezhető maximális pontszám.
Példa:
 
HAROM.BE HAROM.KI
4
1
2 3
3 4 2
4 2 3 1		 15

Vágás - 9. feladat (50 pont) /tesztadatok/

Adott egy fémrúd, amelyet megadott számú darabra kell felvágni úgy, hogy a vágások pontos helyét is tudjuk. A vágások helyét a rúd egyik végétől mért, miliméterben kifejezett értékek adják meg. Olyan vágógéppel kell a feladatot megoldani, amely egyszerre csak egy vágást tud végezni. A vágások tetszőleges sorrendben elvégezhetők. Egy vágás költsége megegyezik annak a darabnak a hosszával, amit éppen (két darabra) vágunk. A célunk optimalizálni a műveletsor teljes költségét.

Feladat:

Készíts programot (VAG.PAS vagy VAG.C), amely
Bemenet:
A VAG.BE szöveges állomány első sora egyetlen egész számot tartalmaz, a vágandó rúd H hosszát (0<H<=10000). A második sorban az elvégzendő vágások N száma van (0<N<=100). A harmadik sor N darab egész számot tartalmaz egy-egy szóközzel elválasztva, az elvégzendő vágások helyeit. A számok szigorúan monoton növekvő sorozatot alkotnak, és mindegyik nagyobb, mint 0 és kisebb, mint H.
Kimenet:
A VAG.KI szöveges állomány első sorába egyetlen számot, a vágási műveletsor optimális összköltségét kell írni! A második sor N darab egész számot tartalmazzon, ami a vágási helyek egy olyan felsorolása legyen, hogy ebben a sorrendben elvégezve a vágásokat, az összköltség optimális lesz.
Példa:
 
VAG.BE VAG.KI
10
4
4 5 7 8		 22
4 7 5 8

ProtoNet - 10. feladat(50 pont) /tesztadatok/

A ProtoNet számítógépes hálózat úgy alakult ki, hogy eredetileg különálló hálózatokat összekapcsoltak. Mindegyik hálózat saját, egyedi protokollt használt. Az egyes részhálózatok az összekapcsolás után is a régi módon, azaz saját protokollt használva működnek. A hálózati hardvert azonban felszerelték olyan szoftverrel, amely képes bármelyik két protokoll közötti váltásra. A teljes hálózat most úgy működik, hogy ha egy X csomópontból közvetlenül egy Y csomópontba kell csomagot küldeni, és X valamint Y nem azonos részhálózathoz tartozik, akkor előbb protokollváltást kell végrehajtani. A hálózati működést optimalizálni szeretnék. Ez azt jelenti, hogy olyan szoftvert kell készíteni, amely meghatározza, hogy ha egy adott A csomópontból egy másik B csomópontba kell küldeni a csomagot, akkor milyen útvonalat kell választani ahhoz, hogy a protokollváltások száma minimális legyen.

Feladat:

Készíts programot (PROTO.PAS vagy PROTO.C), amely
Bemenet:
A PROTO.BE szöveges állomány első sora két egész számot tartalmaz, a csomópontok N számát (0<N<=1000), és a részhálózatok M számát (0<M<=N). A következő M sorban csomópontok sorszámai szerepelnek, minden sort a 0 szám zárja. Az egy sorban felsorolt csomópontok alkotnak egy részhálózatot. Minden csomópont pontosan egy részhálózathoz tartozik. A következő sor a csomópontok közötti közvetlen átviteli kapcsolatok K számát tartalmazza (0<K<=20000). A következő K sor mindegyike egy X Y számpárt tartalmaz, (1<=X, Y<=N, X<>Y), ami azt jelenti, hogy az X és az Y csomópont közvetlenül össze van kötve átviteli csatornával. Az utolsó sor egy A B számpárt tartalmaz, ezek azon csomópont sorszámai (A<>B), amelyek közötti átvitelt vizsgáljuk. Az egyes részhálózatok nem feltétlenül összefüggőek!
Kimenet:
A PROTO.KI szöveges állomány első sorába egyetlen számot kell írni, ami az első részfeladat megoldása. A második sorba egy az A csomópontból a B csomópontba vezető olyan útvonalat kell megadni, amely esetén a protokollváltások száma a lehető legkevesebb! Ha nincs útvonal A és B között, akkor az első sorba a -1 értéket kell kiírni.
Példa:
 
PROTO.BE PROTO.KI
7 3
1 3 5 0
4 2 6 0
7 0
10
1 2
1 3
1 4
2 3
2 5
3 5
3 6
4 7
5 6
5 7
1 7		 1
1 3 5 7