Diákolimpiai válogató 2002



Futár - 1. feladat (40 pont) /tesztadatok/
Egy vállalat futárokat alkalmaz a bizalmas levelek továbbítására. Több városban is lehet futár, és ha egy adott cél városba kell levelet vinni, akkor mindig az a futár viszi a levelet, amelyik a leghamarabb célhoz ér. Minden futár egy nap alatt csak olyan úton haladhat, amely legfeljebb K várost érint.

Feladat:

Készíts programot (FUTAR.PAS, FUTAR.C vagy FUTAR.CPP), amely megadja azon városok sorszámát, amelyekbe 1 nap alatt nem juthat el futár, valamint azt, hogy hány nap kell, hogy biztosan eljusson mindenhova!
Bemenet:
A FUTAR.BE állomány első sorában a városok száma (1<=N<=200), a futár által egy nap alatt bejárható városok száma (1<=K<=N) és a városok közötti utak száma (1<=M<= 10000) van. A következő M sor mindegyike 2 egész számot tartalmaz, amelyek egy-egy utat írnak le: milyen sorszámú városból (1<=X<=N) milyen sorszámú városba (1<=Y<=N) vezet. Az állomány utolsó sorában azon városok sorszáma szerepel egy-egy szóközzel elválasztva, ahonnan indulhat a futár. Az utak kétirányúak, nincs olyan város, ahova futár nem juthat el.
Kimenet:
A FUTAR.KI állomány első sorába azon városok sorszámát kell írni, egy-egy szóközzel elválasztva, ahova nem juthat el futár 1 nap alatt. A második sorba azon napok legkisebb számát kell írni, ahány nap alatt a legtávolabbi városba is elérhet futár!
Példa:
 
FUTAR.BE FUTAR.KI
8 2 9
1 2
1 3
2 4
3 4
2 5
4 6
5 6
2 7
7 8
1 7
6
2


Kannák - 2. feladat (30 pont) /tesztadatok/
Egy gazdának három különböző űrtartalmú tejeskannája van, amelyekbe teli állapot¬ban 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. A gazda észrevette, hogy a kannák közötti öntögetésekkel bizonyos mennyiségű tejet ki tud mérni. Az öntögetések során csak azt kell betartania, hogy tudja, hogy mennyi tej marad abban a kannában, amelyik¬ből tölt és mennyi lesz abban, amelyikbe tölt. Szeretné megtudni, hogy melyek azok a mennyiségek, amelyeket nem tud így kimérni.
Feladat:
Írj programot (KANNAK.PAS, KANNAK.C vagy KANNAK.CPP), 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 egyetlen sorában három pozitív egész szám van, a három kanna űrtartalma. A számok értéke nem nagyobb, mint 39.
Kimenet:
A KANNAK.KI állomány egyetlen sorába azokat az értékeket kell kiírni, amelyek a kezdetben meglévő tej mennyisé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

Üveg - 3. feladat (30 pont) /tesztadatok/

Üvegek újrahasznosítását végző üzembe ládákban érkeznek az üvegek. A feldolgozás végett külön kell válogatni a fehér, a zöld és a barna üvegeket. Minden ládáról tudjuk, hogy hány fehér, zöld illetve barna üveget tartalmaz. A válogatást úgy végzik el, hogy mindhárom fajta számára kijelölnek egy-egy ládát, és minden más ládából az adott fajtájú üveget ebbe a kijelöltbe rakják át.

Feladat:

Készíts programot (UVEG.PAS, UVEG.C vagy UVEG.CPP), amely megad három különböző ládát a fehér, a zöld és a barna üvegek számára úgy, hogy az átpakolás során a lehető legkevesebb üveget kelljen mozgatni!
Bemenet:
Az UVEG.BE állomány első sorában egyetlen egész szám van, a ládák N (3<=N<= 20000) száma. A következő N sor mindegyike három egész számot tartalmaz; F Z B, (0<=F,Z,B<=3000), amelyek egy ládában lévő fehér, zöld, illetve barna üvegek száma.
Kimenet:
A UVEG.KI állomány első és egyetlen sorába három ládasorszámot kell írni (egy-egy szóközzel elválasztva), amelyek .rendre a fehér, a zöld illetve a barna üvegek szá¬mára kijelölt ládák. A ládákat a bementi állománybeli sorszámukkal azonosítjuk, azaz az i-edik láda tartalma az állomány i+1-edik sorában van megadva.
Példa:
 
UVEG.BE UVEG.KI
5
1 6 2
2 4 3
1 3 0
9 2 1
1 2 1

4 1 2

Telep - 4. feladat (30pont) /tesztadatok/

Egy vállalat N városba szeretné eljuttatni termékeit, s ehhez egy telephelyet keres, ahol az árut raktározhatja. Olyan telephelyet szeretne választani, ahonnan a tőle legmesszebb fekvő városba is a lehető leghamarabb eljuthat az áru.

Feladat:

Készíts programot (TELEP.PAS, TELEP.C vagy TELEP.CPP), amely meghatározza azt a várost, ahova a telephelyet tenni kell, valamint azt, hogy mekkora az innen kiinduló legtávolabbi városba vezető út!
Bemenet:
A TELEP.BE állomány első sorában a városok száma (1<=N<=200) és a városok közötti utak száma (1<=M<=10000) van. A következő M sor mindegyike 3 egész számot tartalmaz, amelyek egy-egy utat írnak le: milyen sorszámú városból (1<=X<=N) milyen sorszámú városba (1<=Y<=N) vezet az út és milyen hosszú (1<=H<=200). Minden út kétirányú, és bármely városból bármely másik városba el lehet jutni.
Kimenet:
A TELEP.KI állomány első sorába a telephelyet tartalmazó város sorszámát, második sorába pedig az innen kiinduló leghosszabb út hosszát kell írni.
Példa:
 
TELEP.BE TELEP.KI
6 7
1 2 5
1 3 2
2 4 2
3 4 4
2 5 3
4 6 8
5 6 1

2
6

Lefed - 5. feladat (30pont) /tesztadatok/

Adott a számegyenesen N darab intervallum a bal és jobb végpontjaik [ai,bi] értékeivel, amelyek egész számok. Ki kell számítani a legfeljebb két intervallummal együttesen lefedhető leghosszabb szakasz..

Feladat:

Írj programot (LEFED.PAS, LEFED.C vagy LEFED.CPP), amely megad két (nem feltétlenül különböző) olyan [ai,bi] és [aj,bj] intervallumot, amelyeknek van közös pontjuk és a lehető legnagyobb szakaszt fedik le. Azaz ai <=  aj <= bi <= bj és bj-ai  maximális!
Bemenet:
A LEFED.BE állomány első sorában az intervallumok N száma (2<=N<=10000) van. A következő N sor mindegyikében két egész szám van, a és b, egy szóközzel elválasztva; egy intervallum bal, illetve jobb végpontja (1<=a<b<=20000). A bemenő adatok olyanok, hogy mindig van a feladatban megkövetelt megoldás.
Kimenet:
A LEFED.KI állományba két sort kell írni, egy-egy sorba a feladat megoldását adó két intervallumot (bal és jobb végpontjukat egy szóközzel elválasztva). Ha egy intervallummal lehet lefedni, akkor a két sorba ugyanazt kell írni.
Példa:
 
LEFED.BE LEFED.KI
5
1 3
2 4
3 6
2 5
7 9

1 3
3 6

Nyelvi teszt - 6. feladat (40pont) /tesztadatok/

Egy nyelviskola automatizálni szeretné a vizsgázói által idegen nyelvre fordított mondatok javítását. Ez nehéz feladat, hiszen ugyanannak a mondatnak több helyes fordítása is létezhet. Ennek megoldására azt találták ki, hogy a megoldásként megadott mondatok bizonyos részeire több lehetséges választ is elfogadnak. A zárójelbe tett és | jelekkel elválasztott alternatívák közül bármelyik választható, az utolsó ág üres is lehet. A mondatokat pont, kérdőjel vagy felkiáltójel zárja.
Példa:

(John|He) loved (Mary|her|his girlfriend).

Ebben az esetben az alábbiak bármelyike helyes válasz:
John loved Mary.
John loved her.
John loved his girlfriend.
He loved Mary.
He loved her.

Ez pedig hibás válasz:
He loved her girlfriend.

Feladat:

Írj programot (NYELV.PAS, NYELV.C vagy NYELV.CPP), amely egy adott megoldási kulcs alapján képes eldönteni, hogy bizonyos megoldások helyesek-e.
Bemenet:
A NYELV.BE állomány első sora tartalmazza a megoldási kulcsot (maximum 255 karakter) a fenti szintaxis szerint. A második sorban egyetlen egész szám van, a megoldások száma (1<=N<=300). A következő N sorban a megoldások vannak (soronként maximum 200 karakter). A szavak hossza legfeljebb 50 karakter, amegoldási kulcsban egy szinten legfeljebb 10 alternatíva van.
Kimenet:
A NYELV.KI állományba N sort kell írni, soronként IGEN-t vagy NEM-et, attól függően, hogy a megfelelő válasz helyes volt-e, vagy sem.
Példa:
 
NYELV.BE NYELV.KI
(John|He) loved (Mary|her|his girlfriend).
6
John loved Mary.
John loved her.
John loved his girlfriend.
He loved Mary.
He loved her.
He loved her girlfriend.

IGEN
IGEN
IGEN
IGEN
IGEN
NEM

Gyár - 7. feladat (50 pont) /tesztadatok/

Egy vállalat K városban levő gyárában termel árut, amelyet N városba kell eljuttatni. A szállítási útvonalakat meg kell erősíteni, hogy a nehéz kamionok is közlekedhessenek rajta. Minden városhoz ki kell jelölni egy gyárat, és a gyárból a városba vezető utat, hogy a szállítási útvonalak összhosszúsága a lehető legkisebb legyen!

Feladat:

Készíts programot (GYAR.PAS, GYAR.C vagy GYAR.CPP), amely meghatározza, hogy melyik városba honnan kell szállítani az árut úgy, hogy csak megerősített úton haladjon a kamion a gyár és a város között.
Bemenet:
A GYAR.BE állomány első sorában a városok száma (1<=N<=200), a gyárat tartalmazó városok száma (1<=K<=N) és a városok közötti utak száma (1<=M<=10000) van. A következő M sor mindegyike 3 egész számot tartalmaz, amelyek egy-egy utat írnak le: milyen sorszámú városból (1<=X<=N) milyen sorszámú városba (1<=Y<=N) vezet az út és milyen hosszú (1<=H<=200). Az utolsó sorban K különböző egész szám van: azon városok sorszáma, amelyekben van gyár (1<=Si<=N). Az utak kétirányúak, és minden városhoz el lehet jutni legalább egy gyárból.
Kimenet:
A GYAR.KI állomány első sorába a megerősítendő utak összhosszúságát kell írni. A következő sorokba soronként egy-egy megerősítendő út két végpontjának sorszámát kell írni, egy szóközzel elválasztva. Ha a feladatnak több megoldása is lenne, akkor közülük bármelyik kiírható.
Példa:
 
GYAR.BE GYAR.KI
6 2 7
1 2 5
1 3 3
2 4 2
3 4 4
2 5 3
2 6 8
5 6 1
1 6
9
5 2
1 3
2 4
6 5

Túlélő -8. feladat (50 pont) /tesztadatok/

A túlélőverseny résztvevőinek az a feladata, hogy minél több pontot gyűjtsenek csapatuk számára. Az induláskor kapnak egy térképet, melyen be van jelölve kezdeti pozíciójuk, az állomások helyei, valamint az, hogy az egyes állomások látogatása hány pontot ér. Az a cél, hogy minél több állomást látogassanak meg úgy, hogy az állomásokért kapott pontok összege maximális legyen.

A térkép egy négyzetrácsos hálón van megadva, és az állomások koordinátái pozitív egész számok. A kiindulási pont koordinátái (0,0). A csapat egy (X1,Y1) koordinátájú állomástól minden olyan (X2,Y2) koordinátájú állomáshoz mehet, amelyre X1<=X2 és Y1<=Y2.

Feladat:

Írj programot (TULELO.PAS, TULELO.C vagy TULELO.CPP), amely kiszámít egy olyan útvonalat, amelyen haladva a lehető legtöbb pont gyűjthető össze!
Bemenet:
A TULELO.BE állomány első sorában az állomások N (1<=N<=1000) száma van. A következő N sor mindegyike az X Y P, (0<=X, Y<=10000, 1<=P<= 2000) egész számokat tartalmazza (egy-egy szóközzel elválasztva); ahol (X,Y) egy állomás koordinátái, P pedig az állomás meglátogatásáért járó pont. Az állomásokat a bementi állománybeli sorszámukkal azonosítjuk, azaz az i-edik állomás az állomány i+1-edik sorában van megadva.
Kimenet:
A TULELO.KI állomány első sorába az elérhető maximális pontszámot kell írni. A második sorban egy olyan útvonalat kell megadni, amelyen haladva elérhető a maximális pontszám. Az útvonal az állomások sorszámait tartalmazza abban a sorrendben, ahogy azokat a csapat meglátogatja.
Példa:
 
TULELO.BE TULELO.KI
5
3 1 10
1 2 5
2 4 12
4 5 3
5 3 9

20
2 3 4


Sorbarakás - 9. feladat (50 pont) /tesztadatok/

Egy raktárban N db láda van egy sorban, balról jobbra 1-től N-ig sorszámozva. A ládákat el akarják szállítani, ezért mindegyikre rá van írva, hogy melyik városba kell vinni. A városokat 1-től V-ig sorszámozzák. A raktárban éppen annyi hely van, hogy a ládák elférjenek, és van még egy ládányi hely ideiglenes tárolásra (az ábrán [X]-szel jelölt rész). Ezeket a ládahelyeket is balról jobbra 1-től N-ig sorszámozzuk (kezdetben az i. láda az i. ládahelyen áll), az ideiglenes tárolóhely sorszáma pedig a 0. Mivel a kamion, ami a ládákat elszállítja, először az 1., majd a 2., stb. sorszámú városokba akar menni, és a ládákat csak az ábrán nyíllal jelölt irányból lehet a kamionra pakolni, ezért előzetesen egy targoncának el kell rendeznie a ládákat úgy, hogy bal oldalon legyen az összes olyan, amit az 1. városba, majd amit a 2. városba stb. kell vinni. A targonca egy¬szerre mindig csak egy ládát rakhat át egy üres helyre. Mivel a ládák nagyon nehezek, ezért a targoncának az átrendezést a lehető legkevesebb ládaátrakással kell megoldania.

Feladat:

Készíts programot (SORBA.PAS, SORBA.C vagy SORBA.CPP) amely kiszámítja a sorba rakáshoz szükséges minimális ládamozgatások számát, és megad egy lehetséges mozgatási sorrendet!
Bemenet:
A SORBA.BE állomány első sorában a ládák N (1<=N<=10000) és a városok V (1<=V<= 200) száma van egy szóközzel elválasztva. A második sorban N db szám van egy-egy szóközzel elválasztva, az i. szám, annak a városnak a sorszáma, ahová az i. sorszámú lá¬dát szállítani kell.
Kimenet:
A SORBA.KI állomány első sorába azt az M számot kell írni, ami a minimálisan szükséges mozgatások száma, amellyel a ládák sorba rakhatóak. A következő M sor egy lehetséges minimális mozgatási sorrendet adjon meg: a sorok mindegyike egy számpárt tartalmazzon egy szóközzel elválasztva. Minden i j számpár az i. helyen lévő láda mozgatását jelenti a j-edik helyre.
Példa:
 
   +---------------------------+
 <- [4] [3] [4] [1] [2] [6] [5]|
   | 1.  2.  3.  4.  5.  6.  7.|
   +----------+ [X] +----------+
              |  0. |
              +-----+
SORBA.BE SORBA.KI
7 6
4 3 4 1 2 6 5
9
2 0
5 2
1 5
4 1
3 4
0 3
6 0
7 6
0 7


Töréspróba - 10. feladat(50 pont) /tesztadatok/

Egy ismeretlen anyag szilárdságát kell meghatározni, amely pozitív egész számérték. M számú anyagminta áll rendelkezésre, továbbá van egy berendezés, amellyel töréspróbát végezhetünk anyagmintán. A töréspróba abból áll, hogy a tesztelő eszközt beállítjuk egy adott (egész értékű) erőre és ellenőrizzük, hogy az anyagminta kibírja-e ezt az erőhatást. Ha az anyagminta szilárdsága kisebb, mint a beállított erő érték, akkor az anyagminta tönkremegy és a továbbiakban nem használható töréspróbára, egyébként az anyagminta ép marad és a továbbiakban ismét felhasználható töréspróbára. Ismerjük a vizsgálandó anyag lehetséges legnagyobb szilárdsági értékét. A tesztelő eszköz tetszőleges nagyságú erővel képes töréspróbát végezni. 

Feladat:

Készíts programot (PROBA.PAS, PROBA.C vagy PROBA.CPP), amely kiszámítja, hogy mennyi az a legkevesebb töréspróba, amellyel biztosan kideríthető az anyag szi¬lárdsága, bármekkora egész szám is a megadott határon belül!
Bemenet:
A PROBA.BE állomány egyetlen sorában két egész szám van egy szóközzel elválasztva: M (1<=M<=100) az anyagminták száma, H (2<=H<=1000000) pedig a vizsgálandó anyag lehetséges legnagyobb szilárdsága.
Kimenet:
A PROBA.KI állomány egyetlen sorába a legkevesebb töréspróbák számát kell írni, amellyel az anyag szilárdsága biztosan kideríthető töréspróbákkal, feltéve, hogy a vizsgálandó anyag szilárdsága legfeljebb H, és M darab anyagmintát használhatunk töréspróbára.
Példa:
 
PROBA.BE PROBA.KI
4 200 9