Diákolimpiai válogató 1997


Magasugró verseny  - 1. feladat (15 pont) /tesztadatok/
Egy magasugró versenyen a versenyzők különböző magasságokat próbálnak átugorni. Legalább egyet minden versenyző ugrik. Nem kell mindenkinek minden magasságot megpróbálni, de egy magasságon maximum háromszor próbálkozhat. Ha egyik sem sikerült, akkor kiesik a további versenyből.

A verseny végeredményeként az A versenyző előrébb végez a B versenyzőnél, ha

Feladat:
Készíts programot, amely a verseny ugrásai alapján megadja a versenyzők végső sorrendjét!
Bemenet:
A MAGAS.BE állomány első sorában a versenyzők száma (2*N*40) van, a további soraiban pedig soronként egy-egy magasságon a versenyzők eredményei (legfeljebb 20 sor). Minden sor elején az ugrott magasság, majd a sor végéig az egyes versenyzők kísérletei: egy szóköz, a versenyző sorszáma, a J vagy az R betű (a jó vagy a rossz ugrások azonosítására).
Kimenet:
A MAGAS.KI állományba legfeljebb N sort kell írni, az I. sorba az I. helyen végzett versenyző sorszámát. Ha az I. helyen holtverseny van, akkor az I. sorban több versenyző sorszáma szerepel, egy-egy szóközzel elválasztva.
Példa:
 
MAGAS.BE MAGAS.KI
5
215 1J 3J 4J 5J
220 1R 2R 4R 5R 1R 2R 4R 5R 1J 2R 4R 5R
225 1J 3J
230 1R 3R 1R 3R 1R 3R		 1
3
4 5
2

Kapcsoló  - 2. feladat (18 pont) /tesztadatok/
Három különböző nyomtatót szeretnénk számítógépünkhöz kapcsolni, de a gépnek csak két portja van. Sikerült vásárolni egy olyan 2->3 kapcsolót, amelynek két bemenete a két porthoz, három kimenete pedig a három nyomtatóhoz köthető. Így mind a három nyomtatóra nyomtathatunk, csak a nyomtatás előtt egy kapcsológombbal a megfelelő port->nyomtató kapcsolatot ki kell alakítani, ha a kívánt nyomtató éppen nincs egyik porthoz sem kötve a 2->3 kapcsoló által.
Adott nyomtatandó anyagoknak egy sorozata, megjelölve, hogy az anyagot melyik nyomtatón kell kinyomtatni. A nyomtatókat az A, B és C karakterekkel azonosítjuk. A nyomtatást a megadott sorrendben kell elvégezni, és egyszerre csak egy anyagot nyomtathatunk. Kezdetben egyik nyomtató sincs porthoz kapcsolva.

Feladat:

Készíts programot, amely kiszámítja, hogy minimálisan hány kapcsolás szükséges a bemenetként megadott nyomtatási igény végrehajtásához!
Bemenet:
A KAPCSOLO.BE szöveges állomány első sorában a nyomtatandó anyagok száma (1<=N<=1000) van. A következő sorban N karakterrel adjuk meg az N anyag nyomtató-azonosítóját (A, B és C betűk, elválasztójel nincs közöttük).
Kimenet:
A KAPCSOLO.KI szöveges állomány a nyomtatáshoz szükséges kapcsolások mini-mális számát tartalmazza (egyetlen sor, a szám előtt lehetnek bevezető szóközök).
Példa:
 
KAPCSOLO.BE KAPCSOLO.KI
10
AABACABAAB		 4

Dominók  - 3. feladat (16 pont) /tesztadatok/

Minden egyes dominón két szám található. A dominójátékban úgy tehetünk egymás mellé dominókat, hogy az egyiken levő jobboldali szám illeszkedjen a mellette levő dominó baloldali számához. Például az [1,5][5,3]. Ehhez a párhoz jobbról a [8,3] dominó úgy illeszthető, ha megfordítjuk.

Feladat:

Tegyük le a játék szabályainak megfelelően az összes használható dominót úgy, hogy az első letevése után csak az egyik irányba (tőle jobbra) tehetünk!
Bemenet:
A DOMINO.BE állomány első sorában a felhasználható dominók száma van (1<=N<=100). A következő N sorban pedig egy-egy dominóleírás, a rajta levő két szám, egy szóközzel elválasztva.
Kimenet:
Ha a dominókat le lehet rakni a szabályoknak megfelelően, akkor a DOMINO.KI állomány szerkezete azonos a DOMINO.BE állománnyal, de a dominók sorrendje a le-rakás sorrendjével azonos. A dominókon levő két szám sorrendje is a lerakás sorrendje legyen! Ha a dominókat nem lehet szabályosan lerakni, akkor a DOMINO.KI állomány egyetlen sorból álljon, melyben egy 0 van.
Példa:
 
DOMINO.BE DOMINO.KI
4
1 5
3 2
3 4
2 1		 4
5 1
1 2
2 3
3 4

Szójáték  - 4. feladat (16 pont) /tesztadatok/

Egy szójátékot úgy játszanak, hogy egy kirakandó szöveget a lehető legkevesebb szövegtöredék segítségével kell kirakni. Az egyes szövegtöredékek többször is felhasználhatók, de ekkor többszörösen számítanak az eredményben is.

Feladat:

Készíts programot, amely beolvassa a kirakandó szöveget, majd a felhasználható szövegtöredékeket, s ebből kiszámolja, hogy minimálisan hány szövegtöredékkel lehet kirakni az adott szöveget. Ha a szöveg nem rakható ki, akkor az eredmény legyen 0.
Bemenet:
A SZOVEG.BE szöveges állomány első sorában a kirakandó szöveg (hossza legfeljebb 200 karakter), a másodikban pedig a szövegtöredékek száma (1<=N<=100) van. A további N sor mindegyikében egy szövegtöredék van (hosszuk legfeljebb 20 karakter).
Kimenet:
A SZOVEG.KI szöveges állományba egyetlen számot kell írni, a megadott szöveg kirakásához szükséges szövegtöredékek minimális számát.

Szállodabeosztás  - 5. feladat (20 pont) /tesztadatok/

Az olimpián az egyes csapatok versenyzőit két épületben helyezhetik el. Egyes országok azonban ellenséges viszonyban állnak másokkal, így nem szabad őket egy épületben elhelyezni.

Feladat:

Készíts programot, amely az ellenséges viszonyok ismeretében megadja az épületekre osztást!
Bemenet:
A CSAPAT.BE állomány első sorában a résztvevő országok száma (2<=N<=100) és a két épület szobaszáma (K1+K2<=N) van egy-egy szóközzel elválasztva, a további N sorban pedig egy-egy ország neve. Az ELLENSEG.BE állomány első sorában az ellenséges viszonyok száma (0<=M<=200), a következő M sor mindegyikében pedig két ellenséges ország neve, egy szóközzel elválasztva.
Kimenet:
A CSAPAT.KI állomány első sorába az első épületbe elhelyezendő csapatok számát (L1<=K1), a következő L1 sorba pedig az országok nevét kell írni. Ezután a második épületbe elhelyezendő csapatok száma (L2<=K2), majd L2 sorban az egyes országok neve következik. Ha a feladat nem megoldható, akkor a CSAPAT.KI állományba összesen két sort kell írni, mindkettőben 0 szerepeljen.
Példa:
 
CSAPAT.BE ELLENSEG.BE CSAPAT.KI
?? ?? ??

Kannák  - 6. feladat (16 pont) /tesztadatok/

Egy gazdának három különböző űrtartalmú tejeskannája van, amelyekbe teli állapotban A, B és C liter tej fér. Van továbbá egy negyedik kannája, ennek az űrtartalmát nem ismeri, csak azt tudja, hogy ez a legnagyobb kannája.

Feladat:

Olyan programot kell írni, amely kiszámítja, hogy öntögetéssel milyen mennyiségű tejet nem tud a gazda elkülöníteni a negyedik kannában. Kezdetben a legnagyobb, ismert űrtartalmú kanna tele van, a többi pedig üres.
Bemenet:
A KANNAK.BE állomány három pozitív egész számot tartalmaz az első sorban, a három kanna űrtartalmát. A számok értéke nem nagyobb mint 30.
Kimenet:
A KANNAK.KI állomány első sorába azokat az értékeket kell kiírni, amelyek a kezdetben meglévő tejmennyiségnél kisebbek, de nem állíthatók elő kannák közötti öntögetéssel. Ha minden lehetséges érték előállítható, akkor az egyetlen 0 számot kell kiírni.
Példa:
 
KANNAK.BE KANNAK.KI
13 11 5 4 9

Folyók  - 7. feladat (12 pont) /tesztadatok/

Magyarország összes folyójáról tudjuk, hogy melyik másik folyóba folyik bele.

Feladat:

Készíts programot, amely két konkrét folyóról megadja, hogy összefolynak-e valahol Magyarország területén, s ha igen, akkor melyiknek hány folyón kell átjutnia az összefolyásig.
Bemenet:
A FOLYOK.BE állomány minden sora két folyónevet tartalmaz egy szóközzel elválasztva, az első amelyikbe folyik bele a második.
A FOLYO.BE állomány egyetlen sorában a két megvizsgálandó folyó neve van, egyetlen szóközzel elválasztva.
Kimenet:
A FOLYO.KI állományba két sort kell írni. Az első tartalma IGEN legyen, ha a két folyó összefolyik valahol, illetve NEM, ha nem folynak össze. Ha az első sor IGEN, akkor a második sorba két szám kerüljön egy szóközzel elválasztva: azon folyók száma, amelyeken keresztül a két adott folyó összefolyik. Ha nem folynak össze, a második sor üres.
Példa:
 
FOLYOK.BE FOLYO.BE FOLYO.KI
Duna Rába 
Tisza Hármas-Kőrös
Hármas-Kőrös Kettős-Kőrös
Tisza Zagyva		 Zagyva Kettős-Kőrös IGEN
1 2

Raktár  - 8. feladat (20 pont) /tesztadatok/

Egy áruházlánc két raktárból látja el a hozzá tartozó áruházakat egy adott termékkel. Az A raktárban M, a B raktárban N darab termék van, az áruházak száma M+N. Minden áruházba egy darab terméket kell szállítani, és ismerjük minden áruházra az A, illetve a B raktárból történő szállítás költségét.

Feladat:

Olyan programot kell írni, amely kiszámítja, hogy melyik raktárból kell szállítani az egyes áruházakba, hogy a szállítás összköltsége minimális legyen.
Bemenet:
A RAKTAR.BE állomány első sora az M és N értéket tartalmazza (M+N<=100). A következő két sor mindegyike M+N pozitív egész számot tartalmaz, a szállítási költségeket az A, illetve a B raktárból. Az i. szám az i. áruházba történő szállítás költsége.
Kimenet:
A RAKTAR.KI állomány első sorába a szállítás költségét, a másodikba pedig M+N betűt kell írni: az i. betű a raktár betűjele, amelyikből az i. áruházba kell szállítani.
Példa:
 
RAKTAR.BE RAKTAR.KI
3 4
1 2 3 4 5 6 2
2 1 3 2 1 3 4		 ??

Minimális hálózat  - 9. feladat (16 pont) /tesztadatok/

Magyarország jelentős nagyvárosait benzin továbbítására alkalmas vezetékkel kötjük össze. Benzinvezeték épülhet két város között, de egy újabb város nemcsak egy másik városnál csatlakoztatható a kész hálózathoz, hanem két város közötti csővezeték tetszőleges pontján is. Minden cső vagy két várost köt össze, vagy pedig egy már kiépített csővezetékhez kapcsolódik. A cél a lehető legkevesebb cső felhasználása a csővezeték kiépítéséhez.

Feladat:

Készíts programot, amely beolvassa a városok koordinátáit (valós számok), majd kiírja a minimális hosszúságú csővezetékrendszer hosszát!
Bemenet:
A CSO.BE állomány első sorában a városok száma (2<=N<=100) van, a további N sor pedig egy-egy város x-, illetve y-koordinátáját tartalmazza, egy szóközzel elválasztva.
Kimenet:
A CSO.KI állományba egyetlen számot kell írni, a minimális hosszúságú csővezetékrendszer hosszát, a kiíráskor egészre kerekítve.
Példa:
 
CSO.BE CSO.KI
?? ??

Favágás  - 10. feladat (19 pont) /tesztadatok/

Egy gyümölcsös bináris birsalmafáinak leveleit betegség támadta meg. Szerencsére a fertőzés lassan terjedt. A gyümölcsös gazdája időben észlelte a dolgot. A betegség még nem jutott el más ágakra. A beteg ágak levágásával a fák még megmenthetők.
Minden fára ismerjük a vágások számát. (Természetesen ez nem lehet nagyobb a beteg levelek számánál, de legalább egy.)
A fa legalább egy ággal rendelkezik. A gyökérelemből csak egy (bal oldali) ág indul ki.

Feladat:

Írj a gazdának egy olyan programot, ami megadja minden fához, hogy mely ág(ak)at kell elmetszeni ahhoz, hogy az összes beteg levelet levágjuk, de a megmaradt fának a lehető legtöbb ága (éle) legyen.
Bemenet:
Egy csomópontot négy számmal adunk meg:
Kimenet:
A FAK.KI állományba egy sort kell írni, ami a vágásokat tartalmazza. Egy vágást a csomópont (ez alatti ágat kell elmetszeni) azonosítójával kell megadni. A számokat egy szóköz választja el egymástól.
Példa:
 
FAK.BE FAK.KI
5
0 0 1 -1
1 0 2 3
2 0 4 5
3 0 6 7
4 0 8 9
5 0 10 11
6 0 12 13
7 0 14 15
8 0 16 -1
9 0 17 18
10 0 -1 19
11 1 -1 -1
12 0 20 21
13 0 22 23
14 0 -1 -1
15 0 -1 24
16 0 -1 -1
17 1 -1 -1
18 1 -1 -1
19 1 -1 -1
20 0 -1 -1
21 0 -1 -1
22 1 -1 -1
23 1 -1 -1
24 1 -1 -1		 9 19 11 13 24

Robot  - 11. feladat (16 pont) /tesztadatok/

Egy raktárban robotot üzemeltetnek anyagmozgatásra. A robot csak kijelölt pályákon mozoghat. A pályák rácsos szerkezetet alkotnak, a szomszédos pályák távolsága 1 méter. A raktár téglalap alakú, mérete NxM méter. A szélső robotpályák a raktár falától 1 méter távolságra vannak. A robot alakja kör, aminek átmérője 1.6 méter. A robot középpontjával van a pályán és mindig csak egy rácspontban állhat meg. A raktárban a robot mozgását akadályok gátolják, ezek  mindegyike egy négyzetet foglal el. A robot a következő utasításokat tudja végrehajtani, mindegyiket 1 másodperc alatt.
Feladat:
Készíts programot, amely kiszámítja, hogy egy adott pontból egy adott másik pontba a robot hány másodperc alatt tud eljutni a leggyorsabban.
Bemenet:
A ROBOT.BE állomány első sora az N és M értékeket tartalmazza (N,M<=50). A második sorban négy pozitív egész szám van, x1 y1 x2 y2, ahol (x1, y1) az indulási pont, (x2, y2) pedig a cél pont koordinátái. A további N sor mindegyike M számot tartalmaz, 1-et, ha az adott négyzet akadály, 0 egyébként. Egy akadályt az általa elfoglalt négyzet bal felső sarkának koordinátáival adunk meg. Sor-oszlop koordinátarendszert használunk, azaz a bal felső négyzet koordinátái (0,0), a jobb alsóé pedig (N–1,M–1). A robot kezdetben a felső sor felé néz, célba érkezve irányítása tetszőleges lehet.
Kimenet:
A ROBOT.KI állomány egyetlen számot tartalmazzon, azt, hogy a robot leggyorsabban hány másodperc alatt tud eljutni az indulási pontból a cél pontba. A -1 értéket kell kiírni, ha az akadályok miatt nem tud eljutni a cél pontba a robot.
Példa:
 
ROBOT.BE ROBOT.KI
9 10
7 2 2 7
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0		 19