Nemes Tihamér OKSzTV 2001

Iskolád alapításának évfordulóján nagyszabású ünnepséget szervez. Egy napra sok eseményt tervez. Kiderült, hogy lesznek események, amelyek részben egy időben zajlanak. Ezért meg kell határozni, hogy legkevesebb hány termet kell előkészíteni ahhoz, hogy minden esemény számára legyen terem foglalva, és természetesen az események ne üzközzenek. Minden betervezett eseménynek ismerjük a kezdési és befejezési időpontját, amit percben adtak meg. Ha egy esemény az A perctől a B percig tart, akkor ugyanabba a terembe beosztott bármely másik esemény vagy A-nál korábban ér véget, vagy B-nél később kezdődhet.

Feladat:

Készíts programot (TEREM.PAS vagy TEREM.C), amely kiszámítja, hogy legkevesebb hány terem kell ahhoz, hogy minden betervezett eseményt meg lehessen tartani, továbbá megad egy lehetséges terembeosztást.

Bemenet:

A TEREM.BE állomány első sorában az események N száma van (1<=N<=1000). A következő N sor mindegyikében két egész szám, A és B van egy szóközzel elválasztva. Az A szám egy esemény kezdő, a B pedig ugyanezen esemény befejező időpontja (1 <= A <= B <=1440)

Kimenet:

A TEREM.KI állomány első sorába az összes esemény beosztásához szükséges legkevesebb terem T számát kell írni. A következő T sorban kell megadni a termek beosztását. Egy sorba azon események sorszámait kell írni egy-egy szóközzel elválasztva, amelyek ugyanazon teremben lesznek megtartva (a különböző sorokban lévők pedig mind külön teremben).

Példa:

TEREM.BE	TEREM.KI
8 1100 1200 500 520 510 570 600 630 630 700 700 800 600 800 650 700	4 1 2 4 8 3 5 6 7

Magyarország folyóiról feljegyeztük, hogy milyen másik folyóba folynak bele (pl. a Rába a Dunába, a Sajó a Tiszába, a Hernád a Sajóba, ...). Minden folyó legfeljebb 1 másikba folyhat bele, de lehet hogy egybe sem (pl. Duna, de a Zala sem folyóba folyik bele).

Csónaktúrákat szeretnénk szervezni, de a könnyebbség kedvéért csak úgy, hogy minden folyón a folyás irányában haladjunk.

Feladat:

Készíts programot (TURA:PAS vagy TURA.C), amely megadja, hogy

1. két különböző folyón indult túra hol találkozhat;
2. az első túrát bevárhat-e egy második úgy, hogy nem indul el addig, amíg az első oda nem ér, és ha igen, akkor az elsőnek hány folyón kell addig haladnia (ha ugyanazon a folyón indulnak, akkor 1, ha az egyik folyó éppen belefolyik a másikba, akkor 2, ...

Bemenet:

A TURA.BE állomány első sorában az az N egész szám van, ahány folyóról tudjuk, hogy melyikbe folyik bele (1<=N<=1000). A következő 2*N sor mindegyike egy-egy folyó nevét tartalmazza, a második, negyedik, ... sor azt hogy melyik folyó, a harmadik, ötödik, ... pedig azt, hogy melyikbe folyik bele. Az utolsó két sorban egy-egy folyó neve van, az első és a második túra kezdete.

Kimenet:

A TURA.KI állomány első sorába annak a folyónak a nevét kell írni, ahol a két túra először találkozhat, a sor legyen üres, ha a két túra Magyarországon nem találkozhat (pl. ha az első a Dunán, a második pedig a Tiszán indult). A második sorba azt az egész számot kell írni, ahány folyón az első túrának át kell haladnia, hogy a második túra kezdetéhez érjen. Ha a második nem tudja bevárni az elsőt, akkor ez a szám 0 legyen!

Példa:
 

TURA.BE	TURA.KI
4 Rába Duna Hernád Sajó Szamos Tisza Sajó Tisza Hernád Szamos	Tisza 0

A piramisépítők egy négyzet alapú területre építik a piramist. A terület minden egységnyi négyzetére adott darabszáú kőkockát helyeznek. Amikor egy újabb követ kell elhelyezni, akkor valahonnan a piramis széléről indulnak, és úgy haladnak, hogy minden lépésben pontosan eggyel magasabb szomszéd helyre lépnek. (A szomszédos hely átlósan nem lehet!) Akövet mindig oda taszik, ahonnan nem tudnak szomszédos helyre továbblépni.

Feladat:

Készíts programot (PIRAMIS.PAS vagy PIRAMIS.C), amely megadja a leghosszabb utat, amelyen a piramisépítők egy követ elvihetnek a helyére!

Bemenet:

A PIRAMIS.BE állomány első sorában a piramist tartalmazó négyzet oldalhossza van (1<=N<=100). A következő N sor mindegyike N egész számot tartalmaz, egy-egy szóközzel elválasztva, az egyes pozíciókban lévő kockák számát.

Kimenet:

A PIRAMIS.KI állomány első sorába a leghosszabb út hosszát kell írni (azon lépések számát, ahány lépés alatt egy tetszőleges pozícióból szomszéd helyeken át egyesével lehet felfelé lépkedni), a második sorba pedig az ehhez az úthoz tartozó kezdő pozíció sor- és oszlopindexét. Ha sehonnan sem lehet lépni, akkor az első sorba 0, a második sorba tetszőleges pozíció írandó.

Példa:
 

PIRAMIS.BE	PIRAMIS.KI
6 1 2 2 2 2 2 4 3 4 2 2 1 1 1 5 6 1 8 1 1 1 9 6 7 1 3 4 4 5 1 1 2 1 1 1 1	5 1 1

Egy fazekas műhelyében sorban várakoznak a kiégetésre váró tárgyak. Minden tárgyról tudjuk, hogy mennyi az a legkevesebb idő, ami a kiégetéshez kell. Az égetésre váró tárgyakat az érkezésük sorrendjében kell kiégetni. Egyszerre több tárgyat is rakhatunk a kemencébe, azonban legfeljebb annyit, amennyi a kemence adott kapacitása. Az égetési idő egy menetben mindig a kemencébe rakott tárgyak minimális égetési idejének a maximuma kell legyen.

Feladat:

Készíts olyan programot (FAZEKAS.PAS vagy FAZEKAS.C), amely kiszámítja, hogy legkevesebb mennyi idő kell az összes tárgy kiégetéséhez, továbbá megadja azt is, hogy ezen idő eléréséhez mely tárgyakat kell egy-egy menetben a kemencében együtt égetni.

Bemenet:

A FAZEKAS.BE állomány első sora két egész számot tartalmaz; a tárgyak N (1<=N<=10000) számát és a kemence K (1<=K<=100) kapacitását. A következő N sor mindegyike egy pozitív egész számot tartalmaz; a tárgy minimális égetési idejét, ami nem nagyobb, mint 200.

Kimenet:

A FAZEKAS.KI állomány első sorába az összes tárgy kiégetéséhez minimálisan szükséges időt kell írni. A következő sorok mindegyikébe két egész számot, I-t és J-t kell írni egy szóközzel elválasztva, I az első, J pedig az utolsó tárgy sorszáma, amelyek egyszerre kerülnek a kemencébe.

Példa:
 

FAZEKAS.BE	FAZEKAS.KI
7 3 10 8 20 25 30 12 40	75 1 2 3 4 5 7

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