Nemes Tihamér OKSzTV 2000

Döntő

9-10. osztályosok

2000. március 18.



1. feladat: Autópálya (23 pont) /tesztadatok/
 
Bergengócia nevezetességeit egy kör alakú autópálya köti össze, amely mentén benzinkutak sorakoznak. Berg Egon elhatározta, hogy körbeautózik az úton. Az autóját üres tankkal tudja csak szállítani az egyik benzinkúthoz. Tudjuk, hogy melyik benzinkútnál mennyi benzin van és ismerjük a benzinkutak egymástól való távolságát.

Feladat:

Készíts programot, amely megadja, hogy melyik kúttól kell indulnia Egonnak az ott található teljes benzinkészlettel (biztosan magával tudja vinni), hogy úgy tudjon körbeautózni, hogy autójából ne fogyjon ki a benzin. Az autópálya egyirányú, az I. benzinkúttól csak az (I+1). felé lehet indulni, valamint az N-től az első felé.
Bemenet:
A KORUT.BE állomány első sorában két egész szám áll egyetlen szóközzel elválasztva, N és M, ahol N a kutak számát jelöli (1<=N<=16000), M pedig azt, hogy az autó egy liter benzinnel hány km-t tud megtenni (1<=M<=100). A következő N sor mindegyike két egész számot tartalmaz egy szóközzel elválasztva; az első a következő kút távolságát adja meg km-ben (legfeljebb 1000 km), a második pedig az itt fellelhető benzin mennyiségét (legfeljebb 200 liter).
Kimenet:
A KORUT.KI állomány első sorába az IGEN azót kell írni, ha valamelyik kúttól kezde az autópálya körbeautózható, egyébként a NEM szót. A második sorba azon kutak számát kell írni, melyek bármelyikéből indulva körbe lehet autózni. Ha sehonnan sem lehet körbejutni, akkor ide annak a kútnak a sorszámát kell írni, ahonnan a legmesszebbre el lehet jutni, azaz a legtöbb kutat lehet érinteni. (Ha több megoldás is van, közülük egyet kell megadni.
Példa:
KORUT.BE KORUT.KI
8 10
200 25
200 15
100 5
200 20
300 30
400 45
200 20
200 20
IGEN
4 6 5

2. feladat: Vállalatok (30 pont) /tesztadatok/
Egy vállalat sorsát szeretnénk követni az alábbiakban. Kezdetben egyetlen vállalat létezik. Tetszőleges időpontokban a vállalatot szétbonthatják több önálló vállalatra, illetve önállóan létező vállalatokat újra összevonhatnak. A keletkező vállalatok neve nem lehet azonos egyetlen, korábban létező vállalatéval sem. Egyesüléskor az egyesült, szétbontáskor pedig az egyik keletkező vállalat megtarthatja egyik közvetlen elődje nevét. Ha szétbomlásnál egyetlen vállalat sem keletkezik, akkor a vállalat utód nélkül szűnt meg. Ha egyesüléskor nincs egyesülő, akkor pedig új vállalat keletkezett. Egy vállalatnál egy napon kétféle változás nem lehetséges. Kezdetben egyetlen vállalat létezik.

Feladat:

Készíts programot, amely meghatározza, hogy egy ember, aki vgig ugyanazon a helyen dolgozik, maximum hány vállalat alkalmazottja lehetett az idők során, valamint, hogy mikor volt az, amikor a kiinduló vállalat a legtöbb részre oszlott, s ekkor hány önálló vállalat volt!
Bemenet:
A VALLALAT.BE állomány első sorában az egyesülések / szétbomlások (1<=N<=500) száma, valamint tőlük egy szóközzel elválasztva a kezdetben létező  vállalatok neve található. A következő N sorban vannak a változások. Mindegyik ilyen sor első karaktere plusz-jel (+), ha vállalat-egyesülést ír le, illetve mínusz-jel (--), ha vállalat szétbontást. A jelet annak a vállalatnak a neve követi, ami az egyesült vállalat neve (maximum 10 karakter) lesz, illetve ami a szétbomló vállalat neve volt. Ettől szóközzel elválasztva annak a napnak a sorszáma szerepel, amikor a változás történt. Ettől szóközökkel elválasztva következik a változásban résztvevő vállalatok neve (amik egyesülnek, illetve keletkeznek). A változások időben növekvő sorrendben szerepelnek az állományban. Legfeljebb 2000 különböző vállalat neve szerepel az állományban.
Kimenet:
A VALLALAT.KI állomány első sorába azon vállalatok maximális számát  kell írni, ahol egy ember (munkahelyváltás nélkül) dolgozhatott. A második sorba szóközökkel elválasztva az egyes vállalatok neve kerüljön, ahol dolgozhatott. (Ha több megoldás is van, akkor csak egyet kell megadni.) A harmadik sorba azt a napsorszámot kell írni, amikor a legtöbb vállalat létezett, s tőle egy szóközzel elválasztva az ekkori vállalatszámot. (Ha több megoldás is van, akkor csak egyet kell megadni.)
Példa:
 
VALLALAT.BE VALLALAT.KI
4 ELSO
-ELSO 4 a b c
+d 6 b c
-d 8 e f g
+utolso 10 d e
5
utolso e d b ELSO
8 4

3. feladat: Alkimisták (22 pont) /tesztadatok/
Az alkimisták hosszas kísérleteiket arról, hogy milyen anyagok milyenekké alakíthatók át, gondosan feljegyezték könyveikbe. Bejegyzéseik a lehető legegyszerűbbek voltak: Megadták a kiindulási anyag nevét. majd azt az összetevőt (úgynevezett katalizátort), amit hozzákeverve ehhez létrejött valamilyen végtermék. A bejegyzéseket tanulmányozva megállapították, hogy egyetlen anyag sem állítható elő önmagából, egy vagy több lépésben sem. továbbá nincs két különböző bejegyzés, amelyekben mind az első, mind a második anyag megegyezne. Az anyagok neveit számokkal, míg a katalizátorokat az angol ABC negy betűikkel jelölték A-tól Z-ig.

Egy ilyen bejegyzéssorozatra példa:
 

1 A 2
1 A 3
1 anyagból 2 és 3 keletkezik, ha A-t keverünk hozzá
1 B 4 Ha 1-hez B-t adagolunk, akkor 4 keletkezik
3 F 0 Ha a létrejött 3-hoz F-et keverünk akkor létrejön 0

Az alkimisták aranyat szerettek volna előállítani vasból. Feljegyzéseikben az aranyat 0-val, míg a vasat 1-el jelölték.

Feladat:

Készíts programot, amely megadja, hogy egy adott bejegyzéssorozatban melyek azok a katalizátorok, amelyek feltétlenül szükségesek ahhoz, hogy az alkimista szerint aranyat vasból elő lehessen állítani.
Bemenet:
Az ARANY.BE állomány első sorában megadjuk, hogy hány bejegyzés szerepel a sorozatban, a többi példa pedig a fenti példában szereplő formátumban tartalmazza az egyes bejegyzéseket (a kiindulási anyag száma, szóköz, a katalizátor betűjele, szóköz és a végtermék száma). A használt anyagok száma maximum 200, a katalizátoroké pedig 26. A bejegyzések száma legfeljebb 1000.
Kimenet:
Az ARANY.KI állományba a nélkülözhetetlen katalizátorok betűjelét kell írni, egy sorban szóközzel elválasztva. Ha aranyat nem lehet előállítani semmilyen katalizátorral, akkor NEM LEHET szerepeljen a kimenetben. Ha egyik katalizátor sem nélkülözhetetlen, akkor EGYIK SEM KELL legyen a sor tartalma.
Példa:
 
ARANY.BE ARANY.KI
9
1 A 2
1 A 3
1 B 4
3 F 5
5 G 6
6 A 7
6 B 8
7 C 0
8 D 0
A F G

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