Informatika OKTV 2005

Döntő

11-13. osztályosok

2005. március 12.



1. feladat: Konténer (15 pont) /Tesztadatok/
Egy konténer raktárban N db. konténer van egy sorban tárolva. A konténereket el akarják szállítani, ezért mindegyikre rá van írva, hogy melyik városba kell szállítani. A városokat 1-től 3-ig sorszámozzák. A konténereket át kell rendezni úgy, hogy balról jobbra először 1-essel, majd 2-essel, végül a 3-assal jelölt konténerek álljanak. A raktár majdnem tele van, csak az utolsó konténer után van egy konténer számára szabad hely. A rendezést a konténerek fölött mozgatható robottal végezhetjük, amely egy lépésben kiemel a helyéről egy konténert és átteszi azt a szabad helyre, ezzel az átmozgatott konténer helye lesz szabad.

Feladat:

Írj programot, (KONTENER.PAS, KONTENER.C, ...), amely kiszámítja, hogy legkevesebb hány lépésben lehet rendezni a konténersort, majd megadja a rendezést! A rendezés végén a szabad helynek a sor végén kell lennie!
Bemenet:
A KONTENER.BE állomány első sorában a konténerek N száma van (1<=N<=10000). A második sorN egész számot tartalmaz egy-egy szóközzel elválasztva. Az i-edik szám annak a városnak a sorszáma (1 és 3 közötti érték), ahova az i-edik konténert szállítani kell.
Kimenet:
A KONTENER.KI állomány első sorába a rendezés végrehajtásához minimálisan szükséges lépések M számát kell írni! A következő M sor tartalmazza a sorrendben végrehajtandó mozgatásokat, soronként egy-egy mozgatást! Minden sorban két egész szám legyen egy szóközzel elválasztva; i és j, ami azt jelenti, hogy a lépés során az i-edik helyen lévő konténert a j-edik helyre kell átmozgatni! A kezdetben üres hely sorszáma N+1.
Példa:
KONTENER.BE KONTENER.KI
12
2 1 2 3 1 3 2 3 2 3 1 2
10
9 13
4 9
1 4
5 1
3 5
11 3
6 11
12 6
8 12
13 8

2. feladat: Bérlet (15 pont) /Tesztadatok/
Egy vállalkozónak van egy nagyértékű munkagépe, amit bérbe ad más vállalkozóknak. Sok megrendelése van a következő 200 napra. Minden megrendelés egy (e, u) számpárral adott, ami azt jelenti, hogy az igénylő az e sorszámú naptól az u sorszámú napig kívánja bérelni a gépet. Mivel a bérleti díj minden napra azonos, ezért a bérbeadónak az a célja, hogy olyan megrendeléseket fogadjon el (és teljesítsen), hogy a lehető legtöbb nap legyen bérbe adva a gépe.

Feladat:

Készíts programot (BERLET.PAS, BERLET.C), amely kiszámítja, hogy mely megrendeléseket fogadja el, hogy a gépe a lehető legtöbb napon legyen bérbe adva, és a programod adjon is meg egy beosztást!
Bemenet:
A BERLET.BE állomány első sorában a megrendelések N száma (1<=N<=300) van. A megrendeléseket 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<=200), ami azt jelenti, hogy a megrendelő az e naptól az u napig kívánja bérbe venni a gépet.
Kimenet:
A BERLET.KI szöveges állomány első sora egy egész számot tartalmazzon, a lehető legtöbb nap számát, amelyre a vállalkozó bérbe tudja adni a gépét! A második sorba egy egész számot, az elfogadott megrendelések M számát kell írni! A harmadik sor pontosan M egész számot tartalmazzon, egy-egy szóközzel elválasztva, azoknak a megrendeléseknek a sorszámát (tetszőleges sorrendben), amelyeket a bérbeadó elvállalt! (Több megoldás esetén bármelyik megadható.)
Példa:
 
BERLET.BE BERLET.KI
5
2 7
3 10
13 15
8 11
20 25
19
4
1 4 3 5

3. feladat: Park (15 pont) /Tesztadatok/
A városi vidámpark több részlegből áll. Az egyes részlegeket kétirányú utak kötik össze. Az úthálózat olyan, hogy bármely részlegtől legfeljebb három közvetlen út vezet más részleghez, kivéve a főbejáratot tartalmazó részleget, onnan legfeljebb két másik részleghez vezet közvetlen út. Egy részleghez érve csak a részlegen keresztül lehet másik útra lépni. Minden részleghez el lehet jutni - esetleg más részlegeken keresztül - a főbejáratot tartalmazó részlegtől. Minden részlegbe csak az oda szóló belépőjeggyel lehet bemenni. Kedvezményesen lehet venni olyan belépőjegy köteget, amely minden részlegbe pontosan három jegyet tartalmaz.

Feladat:

Készíts programot (PARK.PAS, PARK.C), amely kiszámít egy olyan séta útvonalat, amely a főbejáratot tartalmazó részlegtől indul, oda ér vissza és minden részleget tartalmaz, de minden részleget legfeljebb háromszor!
Bemenet:
A PARK.BE szöveges állomány első sorában két egész szám van, N a vidámpark részlegeinek száma (1<=N<=1000), M (1<=M<=3000) pedig a részlegeket közvetlenül összekötő utak száma. A részlegeket az 1, ..., N számokkal azonosítjuk, a főbejárat az 1. részlegnél van. A következő M sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva; a b (1<=a, b<=1000, a<>b), ami azt jelenti, hogy az a részleget közvetlen kétirányú út köti össze a b részleggel.
Kimenet:
A PARK.KI szöveges állomány első sorába egy olyan séta útvonalat kell írni, amely a főbejárattal kezdődik és végződik, minden részleget tartalmaz, de legfeljebb háromszor, továbbá az egymást követő részlegek között van közvetlen út! (Több megoldás esetén bármelyik megadható.)
Példa:
 
PARK.BE PARK.KI
9 10
1 2
2 3
2 4
5 4
3 5
4 6
5 6
6 7
7 8
1 8
1 2 4 5 3 5 6 7 8 7 6 5 4 2 1


4. feladat: Malom (15 pont) /Tesztadatok/
A Malomipari Vállalat K malomban őröl és csomagol lisztet. A lisztet N városba kell leszállítani úgy, hogy a szállítási összköltség a lehető legkisebb legyen.

Feladat:

Írj programot (MALOM.PAS, MALOM.C, ...), amely megadja a minimális szállítási költséget, illetve minden városra, hogy oda melyik malomból kell szállítani a lisztet!
Bemenet:
A MALOM.BE szöveges állomány  első sorában a városok száma (1<=N<=100), a malmok száma (1<=M<=N), valamint a közöttük levő utak száma (1<=U<=10000) van. A második sorban M száma, egy-egy szóközzel elválasztva, azon városok sorszáma, ahol malom van. A következő U sor mindegyikében két-két olyan város sorszáma, amelyek között van közvetlen út és a két város közötti szállítási kötség van egy-egy szóközzel elválasztva. A szállítási költség pozitív egész szám, értéke legfeljebb 200.
Kimenet:
A MALOM.KI szöveges állomány első sorába a minimális szállítási költséget kell írni, a második sorba pedig N malomsorszámot, egy-egy szóközzel elválasztva: az I-edik sorszáma annak a városnak a sorszáma legyen, amelyikben levő malomból az I-edik városba kell szállítani a lisztet! Amelyik városba sehonnan sem lehet lisztet szállítani, ott a 0 sorszámot kell kiírni!
Példa:
 
MALOM.BE MALOM.KI
7 2 9
3 6
1 4 10
1 3 10
2 3 10
3 4 10
3 5 30
4 5 5
5 6 10
5 7 10
6 7 30
60
3 3 3 3 6 6 6


5. feladat: Téglalap (15 pont) /Tesztadatok/
Adott a síkon N darab pont és egy ezektől különböző Q pont. Meg kell határozni egy olyan egyenes állású téglalapot (oldalai párhuzamosak a tengelyekkel), amelyre teljesül az alábbi három feltétel:
  1. A Q pont a téglalap belsejében van (nem lehet a határán)
  2. A téglalap mind a négy oldalán pontosan egy-egy pontja van a ponthalmaznak (a négy pont nem feltétlenül különböző)
  3. A ponthalmaz egyetlen pontja sem esik a téglalap belsejébe.

Feladat:

Készíts programot (LAP.PAS, LAP.C), amely kiszámít egy olyan téglalapot, amely teljesíti a három feltétel mindegyikét, ha van ilyen téglalap!
Bemenet:
A LAP.BE szöveges állomány első sorában két egész szám van; A B (0<A, B<=30000), Q pont koordinátái. A második sor egy egész számot tartalmaz, a ponthalmaz pontjainak N (2<=N<=10000) számát. A következő N sor mindegyike két egész számot tartalamaz egy szóközzel elválasztva; X Y (0<X, Y<=30000), a ponthalmaz egy pontjának x- és y-koordinátáját.
Kimenet:
A LAP.KI szöveges állomány első és egyelen sorába négy egész számot kell írni egymástól egy-egy szóközzel elválasztva. Az első két szám a feltételt kielégítő téglalap bal alsó sarkának x és y koordinátája, a második két szám pedig a téglalap jobb felső sarkának x és y koordinátája. Ha nincs olyan téglalap, amely kielégíti a feltételt, akkor a 0 0 0 0 számnégyest kell kiírni. (Több megoldás esetén bármelyik megadható.)
Példa:
 
LAP.BE LAP.KI
4 5
8
1 2
2 5
4 8
5 8
6 7
7 6
5 3
3 4
3 3 6 7


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