Nemes Tihamér OKSzTV'2000

1. feladat: Lift (15 pont) /tesztadatok/

Egy sokemeletes házban szokatlan módon üzemeltetik a liftet. A lift az első szintről indul és mindig felmegy a legfelső szintre, majd visszatér az első szintre. Menet közben megáll minden olyan szinten, amelyik uticélja valamelyik liftben tartózkodó utasnak. Hasonlóan, olyan szinten is megáll, ahonnan utazni szándékozik valaki az aktuális irányban, feltéve, hogy még befér a liftbe (figyelembe véve az adott szinten kiszállókat).

Feladat:

Készíts programot (LIFT.PAS vagy LIFT.C), amely kiszámítja, hogy legkevesebb hány menet szükséges ahhoz, hogy minden várakozó embert elszállítson a lift.

Bemenet:

A LIFT.BE bemeneti állomány első sorában két szám van, N és K. N az épület szintjeinek (2<=N<=500) száma, K (1<=K<=20) pedig a lift kapacitása. A további N sor tartalmazza az egyes szinteken várakozó emberek adatait. Az állomány i-edik sorában azoknak a szinteknek a sorszáma van felsorolva, ahová az (i-1)–edik szintről utazni akarnak. Minden sorban legfeljebb 500 szám lehet, a felsorolást egy 0 szám zárja.

Kimenet:

A LIFT.KI állomány egyetlen sort tartalmazzon, a legkevesebb menetek számát, amely az emberek elszállításához szükséges!

Példa:

2. feladat: Kockavilág (15 pont) /tesztadatok/

Van N (1<=K<=100) db azonos méretű kockánk (1, 2, ..., N számokkal jelöljük). A kockák vagy az asztalon vannak, vagy egy másik kocka tetején.

Van egy robotkar, ami képes fentről megfogni a legfelső kockát és azt egy másik kocka tetejére vagy az asztalra helyezni. A cél az, hogy a robotkar segítségével úgy mozgassuk a kockákat, hogy a 1. legyen legalul, a 2. az 1. kockán legyen, stb.

Bemenet:

A KOCKA.BE bemeneti állomány első sorában N értéke van. A további N sorban található, hogy az adott kocka melyik másik kocka tetején van. Ez a szám 0, ha a kocka az asztalon van. Tehát az állomány i-edik sorában lévő szám azt adja meg, hogy az i-1–edik kocka melyik kocka tetején van. Ha egy kocka a másik tetején van, az csak úgy lehet, hogy az érintkező oldaluk teljesen fedik egymást.

Kimenet:

A KOCKA.KI állomány első sorába a HIBAS szöveget, ha a KOCKA.BE valami oknál fogva nem megfelelő, egyébként a HELYES szót. Az állomány második sorától kezdődően a legkevesebb lépésszámú megoldást kell írni! (Ha több ilyen is van, akkor csak az egyiket.) Minden sorban két szám szerepeljen egy szóközzel elválasztva: melyik kockát melyikre kell tenni!

Példa:

3. feladat: Malac (15 pont) /tesztadatok/

Mohó Marci malacperselyben gyűjti pénzét. Csak fémpénzeket rakott a perselybe, de nem jegyezte fel, hogy milyeneket. Felírta azonban az üres persely súlyát, így meg tudja állapítani a perselyben lévő pénzek összsúlyát. Ismeri továbbá az egyes pénzérmék egyedi súlyát és értékét. Szeretné kiszámítani, hogy mennyi az a legkisebb érték, amelyet a perselye biztosan tartalmaz.

Feladat:

Készíts programot (MALAC.PAS vagy MALAC.C), amely kiszámítja, hogy legkevesebb mekkora értéket tartalmaz a malacpersely!

Bemenet:

A MALAC.BE bemeneti állomány első sorában van a perselyben lévő pénzek S (1<=S<=10000) összsúlya. A második sorban a pénzérmék N (1<=N<=100) száma található. A további N sor mindegyike két pozitív egész számot tartalmaz egy szóközzel elválasztva. Az első szám egy pénzérme értéke (nem nagyobb, mint 200), a második szám pedig a pénzérme súlya (nem nagyobb, mint 1000).

Kimenet:

A MALAC.KI állomány egyetlen sort tartalmazzon, azt a legkisebb értéket, amelyet a malacpersely biztosan tartalmaz!

Példa:

4. feladat: Raktár (15 pont) /tesztadatok/

Egy raktár alapterületét négyzetrácsokra osztották be. Minden mező vagy polcokat tartalmaz, vagy üres. Közlekedni természetesen csak az üres mezőkön lehet. A beosztást úgy alakították ki, hogy bármely két üres mező között pontosan egy út van.

Feladat:

Készíts programot (RAKTAR.PAS vagy RAKTAR.C), amely kiszámítja a raktárban a lehetséges leghosszabb útvonal hosszát.

Bemenet:

A RAKTAR.BE bemeneti állomány első sorában két szám van, M és N (2<=M, N<=200). M a négyzetrácsban az oszlopok száma, N pedig a sorok száma. A további M sor mindegyike pontosan N karaktert tartalmaz (a karakterek között nincs szóköz).A # karakter foglalt, a . (pont) karakter pedig szabad mezőt jelöl.

Kimenet:

A RAKTAR.KI állomány egyetlen sort tartalmazzon, a lehetséges leghosszabb útvonal hosszát! Egy útvonal hossza az útvonalban lévő mezők száma (a két végpontot is beleértve) mínusz 1.

Példa:

5. feladat: Üzenetek (15 pont) /tesztadatok/

A Kozmosz Rt. a stratégiai fontosságú üzenetek továbbítására saját rendszert dolgozott ki. Ha valaki, aki részt vesz a rendszerben és üzenetet kap, köteles azt továbbítani a számára előírt embereknek. A társaságnál az ezirányú kötelezettséget a következőképpen jelölték:

János(Géza,István,Mónika)
Géza(Éva,Lajos)

Jelentésük: Jánosnak továbbítania kell az üzenetet Gézának, Istvánnak és Mónikának, illetve Gézának továbbítania kell az üzenetet Évának és Lajosnak.

A társaság ezen szabályokat egy globális, összevont üzenetközvetítési szabályzattal írja le, ami a példa esetében:

János(Géza(Éva,Lajos),István,Mónika).

Az első ember (János) fogja az üzenetet megkapni a vezérigazgatóságtól, majd továbbítja azokat a számára kiírt embereknek, akik szintén továbbadják azt. Azon emberek, akiknek nincs kijelölve senki, természetesen nem adják tovább az üzenetet senkinek.

A társaság az üzenetközvetítés hatékonyságáról szeretné informálódni, megadott lánc esetén.

Feladat:

Készíts programot (UZENET.PAS vagy UZENET.C), amely kiszámolja az alábbiakat:

A. Egy embernek maximum hány másiknak kell közvetlenül átadnia az üzenetet?

B. Legfeljebb hány emberen keresztül jut el az üzenet valakihez?

C. Hány olyan ember van, akinek nem kell továbbítania az üzenetet?

Bemenet:

Az UZENET.BE állomány első sora tartalmazza a szabályzatot, melyben maximum 1000 ember neve szerepel. A neveket az angol abc kis és nagy betűi jelölik, a szabályzat nem tartalmaz szóköz karaktert. A szabályzatban legalább egy ember szerepel. A szabályzatot leíró karaktersorozatot a # karakter zárja.

Kimenet:

Az UZENET.KI állomány első sorába az A, a második sorába a B, a harmadik sorába pedig a C kérdésre adott választ kell írni.

Példa:

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