Nemes Tihamér OKSzTV'95

Döntő

9-10. osztályosok

1995. 03.18. 10.00-16.00

1. feladat: MIDI (25 pont)

A MIDI (Musical Instrument Digital Interface) számítógépek és szintetizátorok között adatcserére kidolgozott szabvány. A szabvány részben parancsokat tartalmaz a szintetizátor számára egy hang megszólaltatásának elkezdésére vagy befejezésére.
Ez a program például 3 hangot szólaltat meg egyszerre:
0  ON  60
0  ON  70
0  ON  80
10 OFF 60
10 OFF 80
10 OFF 70
10 ON  62
12 OFF 62		 10 időegységig fog szólni a 60-as, a 70-es és a 80-as hang, majd két időegységig a 62-es. A program egy sora tehát a következő információkat tartalmazza: először azt az időpillanatot, amikor a parancsot végre kell hajtani, aztán magát a parancsot (ON esetén bekapcsoltni, OFF esetén kikapcsolni kel a hangot), majd annak a hangnak a sorszámát, amire a parancs vonatkozik
A MIDI programba háromféle probléma fordulhat elő:
a) Tekintsük az alábbi példát:
 
 0 ON  60
10 ON  60
12 OFF 60
20 OFF 60		 Ha meghallgatjuk ezt a programot, akkor nem fogunk két különálló hangot hallani, csak egyet, mégpedig 12 időegységig. Ezen úgy segíthatünk, hogy OFF parancsot illesztünk a programba 1 időegységgel a második ON parancs elé, az eredeti OFF parancsok közül pedig csak a másodikat hagyjuk meg. Így egy rövid szünetet hallunk a két hang között.
b) Egy másik probléma adódik akkor, ha ugyanazon időponthoz tartozó ON és OFF parancs is van a programban:
 
 0 ON  60
10 ON  60
10 OFF 60
20 OFF 60		  0 ON  60
10 OFF 60
10 ON  60
20 OFF 60		 A bal oldali példában 10 időegységig lesz hallható a hang, a jobb oldaliban 20 időegységig, folyamatosan. (Ebben a pédában a problémát okozó utasítások egymás mellett találhatók, de nem kizárt az sem, hogy legyen közöttük ugyanehhez az időponthoz tartozó más utasítás.)
A megoldás mindkét esetben ugyanaz: a problémát okozó OFF parancsot 1 időegységgel a a megfelelő ON parancs elé kell áthelyezni. Ez is egy rövid szünetet eredményez a hang második megszólaltatása előtt.
c) Ha a program véget ér, és valamelyik hang még szól, akkor azt az utolsó időpont után 1 időegységgel ki kell kapcsolni.
Írj programot, ami tetszőleges számú MIDI programot beolvas a MIDI.BE nevű állományból, és a fenti változtatások elvégzése után kiírja MIDI.KI állományba. Az egyes MIDI programokat olyan sorok választják el egymástól, amik csak a sor elején álló -1 számot tartalmazzák. Az utolsó program után -2 áll. A kimenet formátuma a bemenetével egyező.

Az időpont 0 és 65535 közötti egész szám lehet, a parancsokat (ON, OFF) mindig nagybetűvel írjuk, a hangok sorszámai 1 és 127 közötti egész számok. Egy soron belül az időpontot és a parancsot, valamint a parancsot és a hang sorszámát pontosan egy szóköz választja el.

A sorok az időpont szerint nem csökkenő rendben vannak, de az egy adott időponthoz tartozó parancsok sorrendje tetszőleges.

A megoldás során feltehetjük, hogy kezdetben semmilyen hang nem szól, egy hiba kijavítása nem okoz újabb hibát, valamint, hogy nincs hiba a nulladik időpontban.

Példa:
Bemenet
Kimenet
0 ON 60
10 ON 60
12 OFF 60
20 OFF 60
-1
0 ON 60
5 ON 70
10 ON 60
10 OFF 60
15 OFF 70
15 ON 70
20 OFF 60
-2		 0 ON 60
9 OFF 60
10 ON 60
20 OFF 60
-1
0 ON 60
5 ON 70
9 OFF 60
10 ON 60
14 OFF 70
15 ON 70
20 OFF 60
21 OFF 70
-2

2. feladat: Kirándulók (50 pont)

Pista barátunkat kinevezték egy turistaház igazgatójáva. Feladata az, hogy az érkező csoportokat beossza a turistaház szobáiba. Az elosztás során természetesen figyelembe kell vennie a szobák befogadóképességét és a turisták igényeit. Segítsünk barátunknak, írjunk programot! Programunk legyen olyan, hogy szabadon meg lehessen adni, hogy a lehetséges feltételek, megszorítások közül melyeket követeljük meg.
Ennek megfelelően a program elején egy egyszerű menüből lehessen kiválasztani, hogy az alábbi feladatok közül melyiket akarjuk megoldani. (2 pont)
    1. Megadott számú szobánk van, és mindegyiknek ismerjük a maximális befogadóképességét. Tudjuk ezen kívül azt, hogy hány kiránduló érkezik. (A kirándulókat és a szobákat egyaránt egytől kezdődő sorszámozással jelöljük.) (8 pont)
    2. Mint 1., de ezúttal azt is tudjuk, hogy a kirándulók közül hányan lányok, illetve hányan fiúk (jelölés: a lányok sorszáma elé L-t, a fiúk elé F-et írunk). Fiúk és lányok nem kerülhetnek ugyanabba a szobába. (10 pont)
    3. Mint 2., de a turistáknak lehetnek különleges kívánságaik is, azaz megmondhatják, hogy az adott párnak ugyanabban a szobában kell laknia. (14 pont)
    4. Mint 3., de a turisták azt is megmondhatják, hogy csak olyannal kerülhessenek egy szobába, akiket felsoroltak, s a szobájukba mást ne tegyenek. (Ebben az esetben eltekinthetünk attól, hogy esetleg különböző neműek. Például házaspár, család, stb.) (13 pont)


    Az első részfeladatban legfeljebb 1, a 2.-ban és a 3.-ban pedig legfeljebb 2 olyan szoba legyen, ami nincs teljesen feltöltve turistákkal, a 4. részfeladatban ezen kívül az egy szobába teendők mellett a lehető legkevesebb feltöltetlen hely maradjon!

    A program bemenő adatait két szöveges állomány, a SZOBAx.TXT illetve a TURISTAx.TXT írja le. Az első értelemszerűen a rendelkezésre álló szobák adatait, míg a második a turistákról ismert információt tartalmazza. Az állomány nevében szereplő x egy 0 és 9 közötti tetszőleges számjegy lehet - az egy teszthez tartozó állományokat ez azonosítja.

A SZOBAx.TXT állomány formátuma:
Az állomány első sora megadja, hogy hány szoba van a turistaszállóban (maximum 10). Ezután minden sor egy-egy szoba befogadóképességét írja le. (A szobák sorszámozása az állománybeli sorrend szerint történik.)
A TURISTAx.TXT állomány formátuma:
 
Ezt egy olyan sor követi, mely azoknak a pároknak a számát tartalmazza, akiket egy szobában kell elhelyezni. Ezt a megfelelő számú, párokat tartalmazó sor követi. A példában a 3. szeretne egy szobában lakni az 5-kel. 

Végül az olyan csoportok száma következik, akik nem engednek maguk közé idegeneket, amit soronként követ az egyes csoportok leírása. A csoportok leírása egy darabszámmal kezdődik, majd szóközökkel elválasztva a csoportba tartozó személyek sorszámaival folytatódik. A példában az 1., a 7. és a 8. lehet például egy család, akik nem akarnak másokkal osztozni a szobájukon.

 Példa:

8
2
1
3 5
1
3 1 7 8
A program eredménye: (3 pont)
 
A program eredménye az EREDMx.TXT állományba kerüljön, a következő formában. Az állomány minden sora egy szobát írjon le, az alábbiak szerint: 

szobaszám: turista turista turista

Az állománynak a szobasorszámok szerint rendezettnek kell lennie Amennyiben a feladat nem oldható meg, úgy az állomány egyetlen sort tartalmazzon, melyben a következő üzenet legyen olvasható:
  NINCS MEGOLDAS

 Példa:

1: L2
2: F3 F5
3: F4 F6
4: L1 F7 F8

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