A városi rendőrség egy veszélyes bűnöző elfogását tervezi, aki gépkocsival folyamatosan közlekedik a város utcáin. A rendőrségnek korlátozottak a lehetőségei, nem tud például minden kereszteződésbe rendőrt állítani az elfogás érdekében. Ravasz őrmesternek az alábbi kitűnő ötlete támadt. Egy kijelölt K kereszteződésből indulva bejárja a város utcáit és úgy egyirányúsítja azokat, hogy a bűnöző előbb-utóbb úgyis eljut a K kereszteződésbe, ahol egy másik rendőr várakozik, aki elfogja a bűnözőt. A kapitánynak nagyon tetszik az ötlet, de kiköti, hogy Ravasz őrmesternek is be kell tartania a közlekedési szabályokat:Így a megoldás egyértelműen leírható az őrmester útja során érintett kereszteződések sorozatával, mivel ha az útja során egy olyan kereszteződésbe ér, amelyből a B irányában halad tovább, akkor ha ez az utca még nem volt egyirányúsítva, akkor egyirányúsítja, egyébként csak halad tovább az utcában. A város úthálózata összefüggő, azaz minden kereszteződésből el lehet jutni bármely másik kereszteződésbe.
- A már egyirányúsított utcában az őrmester is csak a jelzett irányban közlekedhet.
- Továbbá, ha az A kereszteződésből a B-be vezető utcát akarja egyirányúsítani, azt csak úgy teheti, hogy elmegy az A-ba, ott elhelyez egy behajtani tilos táblát B irányban, ezután elmegy az utcában a B kereszteződésig és ott elhelyezi az A-irányba mutató egyirányú utca táblát.
- Ugyanazon utcában többször is járhat, de csak a már beállított irányban.
Feladat:
Írj programot, amely kiszámít egy olyan bejárási sorozatot, amelyet bejárva és elvégezve az egyirányúsítást, a bűnöző előbb-utóbb feltűnik abban a kereszteződésben, ahonnan az őrmester indult. Minden utcában mindkét irányban lehet közlekedni, de az utcán megfordulni tilos. Kereszteződésben azonban meg lehet fordulni. Az egyirányúsítás következtében csak az a kereszteződés lehet olyan, hogy nem indul belőle egyetlen egyirányú út sem, amelyikből az őrmester elindult.Bemenet:Az ELFOGO.BE állomány első sorában a kereszteződések (1<=N<=200) száma, a második sorában az utcák (1<=M<=10000) száma van. A következő M sor mindegyike egy A B számpárt (1<=A, B<=200) tartalmaz egy szóközzel elválasztva, ami azt jelenti, hogy az A kereszteződésből megy egy (kétirányú) utca a B kereszteződésig. Két kereszteződés között legfeljebb egy utca lehet.Kimenet:Az ELFOGO.KI állomány első sorába az őrmester bejáró útját megadó kereszteződések L számát, a második sorba pedig a bejárt L kereszteződés sorszámát kell írni, egy-egy szóközzel elválasztva.Példa:
ELFOGO.BE ELFOGO.KI 7
10
1 2
1 3
1 4
2 5
2 6
3 7
1 6
2 3
3 4
2 721
1 6 2 7 3 4 3 7 2 5 2 3 2 6 1 4 1 3
Az iskola színháztermében N számú ülőhely van. A következő előadásra M tanuló kérhet jegyet, és mindegyik meghívott tanuló két hely sorszámát megadhatja, mint az általa előnyben részesítettet.Feladat:
Írj programot, amely kiszámítja, hogy legjobb esetben hány tanuló kaphat olyan jegyet, amely az igényléseknek megfelel. A program azt is megadja, hogy mely tanulók kapják az igénylésüknek megfelelő helyeket. Kiszámítandó továbbá, hogy lehet-e az igényeket úgy kielégíteni, hogy a kiosztott helyek összefüggő tartományt alkossanak.Bemenet:Az ULTET.BE állomány első sorában az ülőhelyek száma (1<=N<=200), második sorában az tanulók száma (1<=M<=250) van. A következő M sor mindegyike két különböző ülőhelysorszámot (A B) tartalmaz egy szóközzel elválasztva (1<=A, B<=N). Az állomány i+2-edik sora az i-edik tanuló kívánságát tartalmazza.Kimenet:Az ULTET.KI állomány első sorába azon tanulók T számát kell írni, ahányan a legjobb esetben megkaphatják a két kívánságuknak megfelelő ülőhely valamelyikét. A második sorba egy legjobb kiosztás szerinti ültetést kell írni, tehát T számpárt, amelynek első tagja egy tanuló sorszáma, második tagja pedig azt az általa kívánt ülőhelysorszámot tartalmazza, amit a tanuló kap a legjobb kiosztás szerint. A második sorban a számokat egy-egy szóköz választja el. A harmadik sorba az IGEN szót kell írni, ha van olyan legjobb kiosztás, amely szerint nincs üresen maradt szék a foglalt helyek között, egyébként a NEM szót.Példa:
ULTET.BE ULTET.KI 10
10
1 4
2 4
4 6
6 5
6 7
7 5
3 5
8 10
1 4
4 78
1 1 2 2 7 3 3 4 4 5 5 6 6 7 8 10
3. feladat: Autómentés (35 pont)
Az autómentő szolgálat számítógépes kapcsolatban van az autópálya üzemeltetőjével, aki minden, a pályára belépő autó adatát rögzíti egy adatbázisban. Ezeket az adatokat felhasználva tervezi meg egy autómentő útját a baleset helyszínéig.
Az autópálya egy 2-5 sávos, egyenes és egyirányú forgalmat lebonyolító, elágazás nélküli útszakasz. A 0. sáv a leállósáv, ebben azonban nem közlekedhet semmilyen autó. Az autópályán egy autó helyzetét az autópálya kezdetétől számolva méterekben, illetve a külső sávtól számítva egy sávszámmal tudjuk megadni. Példáult a következő autó helyzetét a (4,2) koordináta adja meg:
sávszámok
v5 4 3 2 X 1 0 leállósáv 1 2 3 4 5 pozíciók a sávon belül ^ az autópálya kezdete Minden autó az alábbi szabályok betartásával közlekedik:
Ha baleset következik be a t időpontban, akkor az autómentő azonnal indul az autópálya bejáratától valamelyik (általa választott) sávban. (Tehát a t+1 időpontban lép be a pálya 1-es pozíciójába.) A baleset helyszíne a 0-s sáv egy pozíciója. A baleset időpontjában lezárják az autópályát, tehát ezt követően nem léphet autó a pályára.
- Minden időpontban, minden pozícióban legfeljebb egy autó tartózkodhat.
- A leállósávban (0. sáv) nem közlekedhet autó.
- Minden autó a számára adott (belépéskor rögzített) sebességgel akar közlekedni. Ez azt jelenti, hogy ha az A autó előtt közvetlenül nincs autó, akkor a sávjában előre halad. Tehát ha a sebessége v és a t időpontban a pálya (x, y) pontjában tartózkodik, akkor a t+1 időpontban az (x1, y) pontba jut, ahol x1=x+v ha a t+1 időpontban nincs előtte a sávban autó az x+1, ..., x+v pozíciókban, egyébként pedig x1=Minimum(x+v, u-1) ha u a legkisebb, x-nél nagyobb olyan pozíció, ahol van autó a t+1 időpontban.
- Ha A utolérte B-t, azaz A pozíciója (x,y) és B pozíciója (x+1, y), akkor A előzni próbálja B-t, ha sebessége nagyobb, mint B sebessége. Először balra, ha nem megy, akkor jobbra próbál előzni. Autó csak akkor válthat sávot, ha nincs mellette autó abban a sávban, amibe lépni akar. Balra előzés azt jelenti, hogy átlép az y+1 sávba az x+1 pozícióba, jobbra előzésnél pedig az y-1 sávra az x+1 pozícióba. Szomszédos sávba csak akkor léphet át az autó, ha nem zavarja az ott közlekedő autók forgalmát, tehát ha abban a sávban az x+1 pozíción nem halad át autó a t, t+1 időben. (Egy autó áthalad a t, t+1 időben az x pozíción, ha a t időpontban az x1, a t+1 időpontban pedig az x2 pozíción van és x1<x<=x2.) Előzés esetén a balra előzőnek van elsőbbsége, tehát ha két autó ugyanazon pozícióba kerülne előzés következtében, akkor az előzést csak a balra előző hajthatja végre, a másik nem. Ha az autó nem tud előzni, akkor természetesen követi az előtte haladót.
Az autómentő hasonló szabályok szerint közlekedik, mint a többi autó, de rá az alábbi szabályok vonatkoznak:
Feladat:
- Semmilyen formában nem befolyásolhatja a többi autó mozgását.
- Minden időpontban eldöntheti, hogy
- Vagy előre halad a sávjában tetszőleges, de a számára rögzítettnél nem nagyobb sebességgel, figyelembe véve az előtte haladó autót.
- Vagy sávot változtat akár balra akár jobbra. (Sávváltáskor nem zavarhatja a többi autó mozgását.)
- Ha az 1-es sávon lépésével áthaladna vagy elérné a baleset helyét jelentő x pozíción, akkor e helyett leléphet a 0-s sáv x pozíciójába (a baleset helyére).
Programodnak a következőkre kell választ adnia:Bemenet:A. Kérdések
B. A baleset időpontjában riadójezést adunk le, ezzel az autóvezetőket arra kötelezve, hogy azonnal álljanak meg. Ekkor indulunk autómenrtőnkkel a baleset helyszínére. A baleset helye mindig a 0-s sáv egy pozíciója, amire az 1-es sávból lép a mentő, és ez a lépés is egy időegységet igényel.
- Hány autó tartózkodik a baleset időpontjában az autópályának a bejáratától a baleset helyszínéig terjedő szakaszán?
- Hol tartózkodnak autók a baleset időpontjában?
Kérdések:
C. A baleset időpontjában valamennyi autó jelzést kap, hogy ezt követően tilos sávot változtatniuk, továbbá állandó sebességgel kell haladniuk, ami eggyel kisebb, mint az autómentő sebessége.
- Minimálisan mennyi idő alatt juthat el az autómentő a baleset színhelyére?
- Hogyan juthat el az autómentő a baleset helyszínére?
Kérdés:
D. Nem korlátozzuk az autók forgalmát, a továbbhaladó forgalomban próbálunk meg eljutni a baleset helyszínéhez.
- Minimálisan mennyi idő alatt juthat el az autómentő a baleset színhelyére?
Kérdés:
- Minimálisan mennyi idő alatt juthat el az autómentő a baleset színhelyére?
Az AUTO.BE állomány első sorában a sávok K (1<K<=5) száma van. A második sorban az autómentő maximális sebessége áll. A harmadikban a baleset időpontja és pozíciója van egy szóközzel elválasztva. A baleset időpontja kisebb, mint 1000.Kimenet:A további sorok mindegyike egy autó adatait, három pozitív egész számot tartalmaz: T S V, ahol T a pályára lépés időpontja, S az a sáv, amelyiken belépett az autó, V pedig a megengedett legnagyobb sebessége. Az utolsó sor 3 darab 0-t tartalmaz. Minden sebességérték nagyobb, mint 0 és kisebb, mint 100. Az adatok az állományban a belépési idő szerint nemcsökkenő sorrendben vannak.
Az állomány maximum 4000 soros lehet, az autópálya pedig 4000 m hosszú lehet.
Az AUTO.KI állományban az A és B részfeladathoz 2, a többiekhez 1 sor tartozik. Ha a program valamelyik részfeladat kérdésére nem tud válaszolni, akkor a részfeladathoz üres sort kell írni.Példa::Az első sorba egy egész számot, a baleset időpontjában az autópályának a bejáratától a baleset helyszínéig terjedő szakaszán tartózkodó autók számát kell írni. A második sorba ezen autók koordinátáit kell kiírni egy-egy szóközzel elválasztva. Ha nincs autó a pálya ezen szakaszán, akkor üres sort kell írni.
A harmadik sorba azt a legkisebb időt (baleset helyszínére érés időpontja - a baleset időpontja) kell írni, amely ahhoz szükséges, hogy az autómentő eljusson a baleset helyére, feltéve, hogy minden autó áll a baleset bekövetkezése után. Ha nem lehet eljutni, akkor a -1 értéket kell kiírni. A negyedik sorba azt a koordinátasorozatot kell kiírni, amelyeken keresztül az autómentő eljut a baleset helyére. Az utolsó koordinátapár a baleset helyszínének koordinátái, tehát Bx 0, ha a baleset a Bx helyen történt. Ha nem lehet eljutni, akkor üres sort kell írni.
Az ötödik sorba egyetlen egész számot, azt a legkisebb időt kell írni, amely ahhoz szükséges, hogy az autómentő eljusson a baleset helyére, feltéve, hogy az autók a baleset bekövetkezése után nem válthatnak sávot és állandó (a mentő sebessége-1) sebességgel közlekednek. Ha nem lehet eljutni, akkor a -1 értéket kell kiírni.
A hatodik sorba egyetlen egész számot, azt a legkisebb időt kell írni, amely ahhoz szükséges, hogy az autómentő eljusson a baleset helyére, ha együtt kell haladnia a forgalommal. Ha nem lehet eljutni, akkor a -1 értéket kell kiírni.
AUTO.BE AUTO.KI 4
4
5 13
1 3 1
1 1 1
2 3 1
3 1 1
3 4 2
4 2 3
4 3 1
4 1 3
0 0 08
2 1 3 1 5 1 4 2 2 3 4 3 5 3 5 4
7
1 2 3 2 4 1 5 2 6 1 9 1 13 0
5
6