Nemes Tihamér OKSzTV 2001

Magyarország folyóiról feljegyeztük, hogy milyen másik folyóba folynak bele (pl. a Rába a Dunába, a Sajó a Tiszába, a Hernád a Sajóba, ...). Minden folyó legfeljebb 1 másikba folyhat bele, de lehet hogy egybe sem (pl. Duna, de a Zala sem folyóba folyik bele).

A folyó szennyezettségének megállapításához szükség van arra, hogy megállapítsuk, melyik folyóba honnan érkezhet szennyezett víz.

Feladat:

Készíts programot (FOLYO.PAS vagy FOLYO.C), amely megadja, hogy

A. egy folyóba mely folyókból érkezhet víz (akár más folyón keresztül is);
B. egy folyóba került szennyezés mely más folyókat szennyezhet meg!

Bemenet:

A FOLYO.BE állomány első sorában az az N egész szám van, ahány folyóról tudjuk, hogy melyikbe folyik bele (1<=N<=1000). A következő 2*N sor mindegyike egy-egy folyó nevét tartalmazza, a második, negyedik, ... sor azt hogy melyik folyó, a harmadik, ötödik, ... pedig azt, hogy melyikbe folyik bele. Az utolsó sorban egy folyó neve van, az, amelyről az A és a B kérdés szól.

Kimenet:

A FOLYO.KI állomány első sorába azoknak a folyóknak a K számát kell írni, amelyekből érkezhet víz a FOLYO.BE állomány utolsó sorában levő folyóba. A következő K sorba kell kiírni soronként a folyók nevét. A K+1-edik sorba azoknak a folyóknak az L számát kell írni, amelyekbe eljuthat a szennyeződés a megadott folyóból! Az ezt követő L sorba kell kiírni soronként a folyók nevét.

Példa:

FOLYO.BE	FOLYO.KI
4 Zagyva Tisza Sajó Tisza Tarna Zagyva Gyöngyös Tarna Zagyva	2 Tarna Gyöngyös 1 Tisza

A porcelángyár égetőkemencéjéhez futószalagon érkeznek az égetésre váró tárgyak. Minden tárgynak ismert a súlya és a kiégetéséhez minimálisan szükséges idő. Az égetésre váró tárgyakat az érkezésük sorrendjében kell kiégetni. Egyszerre több tárgyat is rakhatunk a kemencébe, az összsúlyuk azonban nem haladhatja meg a kemence kapacitását. Az égetési idő egy menetben mindig a kemencébe rakott tárgyak minimális égetési idejének a maximuma kell legyen.

Feladat:

Készíts olyan programot (KEMENCE.PAS, KEMENCE.C), amely kiszámítja, hogy legkevesebb mennyi idő kell az összes tárgy kiégetéséhez, továbbá megadja azt is, hogy ezen idő eléréséhez mely tárgyakat kell egy-egy menetben a kemencében együtt égetni.

Bemenet:

A KEMENCE.BE állomány első sora két egész számot tartalmaz; a tárgyak N (1<=N<=10000) számát és a kemence K (1<=K<=1000) kapacitását. A következő N sor mindegyike két egész számot tartalmaz; egy tárgy S (1<=S<=1000) súlyát és E (1<=E<=100) minimális égetési idejét.

Kimenet:

A KEMENCE.KI állomány első sorába az összes tárgy kiégetéshez minimálisan szükséges időt kell írni. A következő sorok mindegyikébe két egész számot, I-t és J-t kell írni egy szóközzel elválasztva, I az első, J pedig az utolsó tárgy sorszáma, amelyek egyszerre kerülnek a kemencébe.

Példa:
 

KEMENCE.BE	KEMENCE.KI
6 10 3 10 2 12 7 20 5 15 3 11 2 16	46 1 1 2 3 4 6

Egy hegymászó megkapta egy hegység domborzati térképét, amely egy négyzetrácsháló egyes pontjaiban tartalmazza a felszín tengerszint feletti magasságát. A hegymászás során a hegység tetszőleges pontjáról indulhat, s minden lépésben a 4 szomszédos hely valamelyikére léphet (tehát átlósan nem). Egy emelkedő út olyan lépéssorozat, amikor minden egyes érintett hely magasabb az előzőnél, az út hossza pedig a megtett lépések száma.

Feladat:

Készíts programot (HEGYSEG.PAS vagy HEGYSEG.C), amely megadja a leghosszabb utat, amelyen egy hegymászó folyamatosan felfelé haladhat! Ha több megoldás is van, elég csak egyet megadni.

Bemenet:

A HEGYSEG.BE első sorában a hegység domborzati térképét tartalmazó téglalap sorainak és oszlopainak száma van (1<=N, M<=100). A következő N sor mindegyike M egész számot tartalmaz egy-egy szóközzel elválasztva, az egyes pozíciók tengerszint feletti magasságát.

Kimenet:

A HEGYSEG.KI állomány első sorába a leghosszabb út hosszát kell írni (azon lépések számát, ahány lépés alatt egy tetszőleges kezdőpozícióból szomszéd helyeken át folyamatosan lehet felfelé lépkedni), a második sorba pedig az ehhez tartozó kezdő pozíció sor- és oszlopindexét. Ha sehonnan sem lehet lépni, akkor az első sorba 0, a második sorba tetszőleges pozíció írandó.

Példa:
 

HEGYSEG.BE	HEGYSEG.KI
6 8 2 2 1 2 2 2 1 1 4 3 6 9 2 1 1 1 5 1 7 8 1 8 1 1 1 1 1 1 6 7 1 1 1 3 4 4 5 1 1 1 1 2 1 1 1 1 1 1	6 1 3

Kutatók megfigyelték, hogy egyes vírustörzsek nagyon sok, akár több milliárd variánst is tartalmazhatnak. Az egy törzshöz tartozó vírusok felsorolása nagyon költséges lenne, azonban azt is észrevették, hogy a variánsok nagyon hasonlítanak egymásra. Ez lehetővé teszi, hogy az informatikában jól ismert módszer alkalmazásával, úgynevezett víruskifejezéssel adjuk meg az egy törzshöz tartozó vírusokat.

Minden víruskifejezés olyan jelsorozat, amely az (angol) ábécé 'A' .. 'Z' nagybetűi, a '[', ']' kezdő- és végzárójel, a '-' mínusz jel és a '|' függőleges vonal jelekből a következő három szabály véges sokszori alkalmazásával kapható:
 

1. Minden betű ('A'-tól 'Z'-ig) víruskifejezés, és a betűvel azonosított vírust jelöli. A '-' jel is víruskifejezés, amely az üres (egyetlen betűt sem tartalmazó) jelsorozatot jelöli.
2. Ha <alfa> és <béta> víruskifejezés, akkor <alfa><béta> is víruskifejezés, és pontosan azokat a vírusokat jelöli, amelyek XY alakúak, ahol X egy <alfa> által, Y pedig egy <béta> által jelölt vírus.
3. Ha <alfa₁>, <alfa₂>, ..., <alfa_k> víruskifejezések (k>=2), akkor [<alfa₁>| <alfa₂>| ...|<alfa_k>] is víruskifejezés, és pontosan azokat a vírusokat jelöli, amelyeket valamelyik <alfa_i> (i=1, ..., k) alternatíva jelöl.

Például az [A|B-]D[BB|A[B|C]][X|-] víruskifejezés a következő 12 vírust jelöli: ADBBX, ADBB, ADABX, ADAB, ADACX, ADAC, BDBBX, BDBB, BDABX, BDAB, BDACX, BDAC. A [A|B][A|B|-] 31-szer, víruskifejezés az összes olyan vírust jelöli, amely legfeljebb 32 betűből áll, és minden betű A vagy B.

Feladat:

Készíts programot (VIRUS.PAS vagy VIRUS.C), amely a bemenetben adott víruskifejezés és karaktersorozatokra eldönti, hogy azok a víruskifejezés által jelölt vírustörzshöz tartoznak-e!

Bemenet:

A VIRUS.BE állomány első sorában egy szabályos víruskifejezés van, amelyben a betű és - karakterek száma legfeljebb 100. A víruskifejezés után egy pont (.) karakter van. A második sorban egy egész szám, a vizsgálandó elemek M száma van (1<=M<=10). A következő M sor mindegyikében egy legfeljebb 100 karakterből álló karaktersorozat áll, amelyekről el kell dönteni, hogy a víruskifejezés által jelölt vírustörzsbe tartoznak-e.

Kimenet:

A VIRUS.KI állomány pontosan M sort tartalmazzon. A megfelelő sorban a VIRUS szó legyen, ha a vizsgált karaktersorozat a vírustörzsbe tartozik, egyébként pedig az a legnagyobb K szám, amelyre igaz, hogy van olyan vírus, amelynek első K betűje megegyezik a vizsgált jelsorozat első K betűjével.

Példa:
 

VIRUS.BE	VIRUS.KI
[A|B|-]D[BB|A[B|C]][X|-]. 3 BDAX AAAAA BDBBY	VIRUS 1 4

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