Nemes Tihamér OKSzTV 2005

Egy csapatversenyben N csapat vesz részt, a csapatokat 1 és N közötti sorszámukkal azonosítjuk. Ismerjük M mérkőzés eredményét

Feladat:

Írj programot (VERSENY.PAS, VERSENY.C, ...) az alábbi feladatokra!

1. Adj meg két csapatot, amelyek már legyőzték egymást!
2. Add meg azokat a csapatokat, kik már játszottak, de még senki nem győzte le őket!
3. Adj meg egy csapatot, amely "közvetve legyőzte magát" (azaz pl. A ilyen, ha A legyőzte B-t, B legyőzte C-t, ..., Y legyőzte Z-t, s Z legyőzte A-t)!
   

Bemenet:

A VERSENY.BE szöveges állomány első sorában a csapatok N  száma (2<=N<=100) és a mérkőzések M száma (1<=M<=10000) van. A következő M sorban egy-egy mérkőzés eredménye van: két szám (i és j) egy szóközzel elválasztva. Jelentése: az i-edik csapat legyőzte a j-edik csapatot.

Kimenet:

A VERSENY.KI szöveges állományba 3 sort kell írni, a 3 részfeladat megoldását. Az első sorbaa két csapat sorszámát kell írni, egyetlen szóközzel elválasztva, a második sorba az összes kért csapat sorszámát kell írni! A harmadik sorba egyetlen csapat sorszáma kerüljön! Mind a három sorra igaz, hogy ha nincs megfelelő csapat, egy üres sornak akkor is ki kell kerülnie az állományba!

Példa:

VERSENY.BE	VERSENY.KI
6 7 1 2 1 3 3 1 2 4 4 1 5 2 5 3	1 3 5 1

Árpád-házi királyokról tároljuk születési, illetve uralkodási adataikat. Csak olyan esetben vizsgálunk, amikor folyamatosan volt király, egyszerre csak egy, és mindegyik király csak egy időintervallumban uralkodott.

Feladat:

Készíts programot (KIRALY.PAS, KIRALY.C, ...), amely megadja az alábbiakat!

1. Mettől meddig volt a leghosszabb időszak, amikor olyan uralkodók voltak, akik az apjukat követték a trónon (beleszámítva a legelsőt, aki még nem az apját követte)?
   
2. Hányan voltak legtöbben testvérek, akik mindegyike uralkodott valamikor?
   
3. Hány olyan király volt, akinek volt gyermeke, de egyik sem lett király?
   

Bemenet:

A KIRALY.BE szöveges állomány első sorában az uralkodók N száma van (1<=N<=100). A következő N sor mindegyike 3 adatot tartalmaz: a király uralkodásának kezdő- és végző évét időrendben, valamint a nevét, egy-egy szóközzel elválasztva (a nevek biztosan különbözőek). A következő sorban az Árpád-ház családtagjainak leszármazási kapcsolatai M száma van (1<=M<=1000). Az ezt követő 2*M sor páronként egy-egy szülői kapcsolatot tartalmaz: a pár első tagja a szülő, a második pedig a gyerek nevét.

Kimenet:

A KIRALY.KI szöveges állományba 3 sort kell írni, a 3 részfeladat megoldását! Az első sorba két időpontot kell írni: az A feladatban kért időszak kezdő- és végző évét! Ha senki sem az apját követte a trónon, akkor ez a sor legyen üres! A második sorba egyetlen szám, a B feladat megoldása kerüljön! A harmadoik sorba a C feladatban kér királyok számát kell írni!

Példa:
 

KIRALY.BE	KIRALY.KI
7 1046 1060 I. András 1060 1063 I. Béla 1063 1074 Salamon 1074 1077 I. Géza 1077 1095 Szent László 1095 1116 Könyves Kálmán 1116 1131 II. István 10 Vazul I. András Vazul I. Béla Vazul Levente I. András Salamon I. Béla I. Géza I. Béla Szent László I. Géza Könyves Kálmán Szent László Piroska Könyves Kálmán László Könyves Kálmán II. István	1095 1131 {Könyves Kálmán és fia} 2 {pl. I. András és I. Béla} 1 {Szent László lánya}

Egy város utcái NxM-es négyzethálós elrendezésűek. Minden kereszteződésben pontosan 4 utca találkozik, kivéve esetleg a város szélén lévő kereszteződéseket. A kereszteződéseket a sor-, illetve az oszlop-koordinátájuk adja meg, mindkettőt 1-től sorszámozzuk, a bal felső sarok az (1,.1) koordinátájú pont. Egyes utcák egyirányúak, mások pedig kétirányúak. Az utcák irányítottságát a kereszteződésekben adjuk meg, egy-egy 8 bites számmal az alábbi táblázat szerint (a biteket hátulről sorszámozva):

1. bit: 1-es, ha a felfelé vezető utcából lehet a kereszteződésbe jutni (lefelé irány)
2. bit: 1-es, ha a felfelé vezető utcába lehet menni a kereszteződésből (felfelé irány)
3. bit: 1-es, ha a jobbra vezető utcából lehet a kereszteződésbe jutni (balra irány)
4. bit: 1-es, ha a jobbra vezető utcába lehet menni a kereszteződésből (jobbra irány)
5. bit: 1-es, ha a lefelé vezető utcából lehet a kereszteződésbe jutni (felfelé irány)
6. bit: 1-es, ha a lefelé vezető utcába lehet menni a kereszteződésből (lefelé irány)
7. bit: 1-es, ha a balra vezető utcába lehet a kereszteződésbe jutni (jobbra irány)
8. bit: 1-es, ha a balra vezető utcába lehet menni a kereszteződésből (balra irány)

Feladat:

Készíts programot (UT.PAS, UT.C), amely a kereszteződések ismeretében megadja, hogy a tervezett úthálózat mely kereszteződésekben hibás!
A lehetséges - egyszerű - hibák:

• a kereszteződésből semerre sem lehet kimenni;
• a kereszteződésekbe sehonnan nem lehet bemenni;
• a kereszteződés valamelyik utcánán sem bejönni, sem kimenni nem lehet;
• egy utca két végpontján levő kereszteződésekben ellentmondó adatok vannak az utcáról (ekkor mindkét kereszteződés hibás!);
• a városból sehol sem lehet kijutni (ekkor a (0,1) kereszteződést tekintjük hibásnak);
• a városba sehol sem lehet kívülről bejönni (ekkor (1,0) kereszteződés a hibás).
  

Bemenet:

Az UT.BE állomány első sorában az úthálózatot leíró négyzetháló sorai (1<=N<=100) és oszlopai (1<=M<100) száma van. A következő N sor mindegyike pontosan M számot tartalmaz: az egyes kereszteződéseket leíró 8 bites számok tízes számrendszerbeli alakját.

Kimenet:

Az UT.KI szöveges állomány első sorába a hibás kereszteződések K számát kell írni! A következő K sor mindegyikébe egy-egy hibás kereszteződés sor- (1<=sor<=N) és oszlopindexe (1<=oszlop<=M), egyetlen szóközzel elválasztva, vagy pedig az 1 0, illetve a 0 1 kód (az utolsó két hiba esetén)! Ha egy kereszteződés több szempontból is hibás, akkor is csak egyszer szabad kiírni!

Példa:
 

UT.BE	UT.KI
3 3 60 239 255 63 237 179 5 254 195	5 2 1 2 2 2 3 3 1 3 2

Egy népszerű zenekar a következő évre vonatkozó fellépéseit tervezi- Sok meghívása van fellépésre, ezek közül kell a zenekarnak választani, hogy melyiket fogadja el. Minden fellépés pontosan egy napot foglal el. Minden beérkezett meghívási igény egy (e, u) számpárral adott, ami azt jelenti, hogy az igénylő azt szeretné, hogy a zenekar olyan k sorszámú napon tartson nála koncertet, hogy e<=k<=u. A zenekarnak az a célja, hogy a lehető legtöbb fellépése legyen.

Feladat:

Készíts programot (ZENEKAR.PAS, ZENEKAR.C), amely kiszámítja, hogy mely meghívásokat fogadja el, hogy a következő évben a lehető legtöbb fellépése legyen, és a programod adjon is meg egy beosztást!

Bemenet:

A ZENEKAR.BE állomány első sorában a meghívások N száma (1<=N<=1000) van. A meghívásokat az 1, ..., N számokkal azonosítjuk. A következő N sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva; e u (1<=e<=u<=365). Az i-edik meghívás az állomány (i+1)-edik sorában van.

Kimenet:

A ZENEKAR.KI szöveges állomány első sora egy egész számot tartalmazzon, a vállalható legtöbb fellépések M számát! A következő M sor mindegyike két egész számot tartalmazzon, egy szóközzel elválasztva! Az első szám egy elfogadott meghívás sorszáma legyen, a második pedig annak a napnak a sorszáma, amelyik napon teljesíti a zenekar a fellépést! (Több megoldás esetén bármelyik megadható.)

Példa:
 

ZENEKAR.BE	ZENEKAR.KI
6 2 4 1 4 3 5 1 3 3 5 2 5	5 4 1 2 2 3 3 5 4 6 5

Elérhető összpontszám: 75 pont + 25 pont a 2. fordulóból