Nemes Tihamér OKSzTV'2000

Második forduló

9-10. osztályosok

2000. január 15. 900-1400


1. feladat: Gombaszedés (22 pont) /tesztadatok/

Józsi bácsi hétvégénként nagy szeretettel jár a közeli erdőbe gombászni. Valamelyik hátizsákjával szokott elindulni, és ebbe a zsákba próbál meg minél több gombát szedni. Az erdőben háromféle gomba terem meg: Csiperke, Rókagomba és Lila pereszke. Józsi bácsi az évek során a következő módszert alakította ki a gombák leszedésére:

A. Mindaddig nem szed Lila pereszkét, amíg még van az erdőben Csiperke gomba.

B. Először mindig a legnagyobb (legnehezebb) gombát szedi le (persze, ha ez nem ütközik az A. ponttal).

C. Azonos súlyú gombák esetén először Csiperké(ke)t, majd a Rókagombá(ka)t, és legvégül a Lila pereszkéket szedi le.

Ha adott az erdő gombaállománya (minden gomba súlya dekagrammban és fajtája), és Józsi bácsi hátizsákjának kapacitása (azaz hány dekagramm gombát képes a zsákban tárolni) határozzuk meg, hogy hány dekagramm gombát tud (és ezekből fajtánként mennyit) leszedni. Tudjuk azt is, hogy Józsi bácsi nem vág ketté gombát azért, hogy a zsákja még jobban tele legyen (tehát csak egész gombák vannak a zsákban). Ha egy nagyobb gomba már nem fér bele a zsákba, azt kihagyja.

Feladat:

Készíts programot (GOMBA.PAS vagy GOMBA.C) a gombák zsákba pakolására!


Bemenet:

A GOMBA.BE állomány első sorában a gombák száma van (maximum 1000), a másodikban pedig a zsák kapacitása (maximum 100000), a többi sor mindegyikében egy gomba jellemzői vannak: a fajta (a következő karakterek valamelyike: C, R vagy L) és a súly dekagrammban (1 és 100 között) egy szóközzel elválasztva.


Kimenet:

A GOMBA.KI állományba a leszedett gombák darabszámát és súlyát kell írni (egy szóközzel elválasztva). Az első sorba az összes leszedett gomba, a másodikban csak a csiperke, a harmadikban a rókagomba, a negyedikben pedig a lila pereszke darabszámát és a súlyát.
Példa:
GOMBA.BE GOMBA.KI
6
25
C 4
R 8
L 12
C 10
L 2
R 2
4 24
2 14
2 10
0 0


2. feladat: Hálózat (20 pont) /tesztadatok/
Egy számítógépes hálózat kiépítése a következőképpen történik: Kezdetben egy gépből áll a hálózat. Egy új gép bekapcsolásakor azt pontosan 1 db, már a hálózatban levő géppel kötik össze, ami kétirányú kapcsolatot biztosít a két összekötött gép között.

Két gép távolságán a legkevesebb közvetlen összekötést tartalmazó összekötést értjük. A hálózat átmérőjének nevezzük a hálózatban levő gépek közül a két legtávolabbi távolságát.

Feladat:

Készíts programot (HALOZAT.PAS vagy HALOZAT.C), ami kiszámítja, hogy N db gép esetén mekkora lesz a hálózat átmérője!


Bemenet:

A HALOZAT.BE állomány első sorában N (1<=N<=100) értéke található. Az állomány I. sorában annak a számítógépnek a J (J<I) sorszáma van, amelyhez az I. számítógépet kötik a hálózatban.


Kimenet:

A HALOZAT.KI állományba egyetlen számot kell írni, a hálózat átmérőjét a teljes kiépülés után.


Példa

HALOZAT.BE HALOZAT.KI
7
1
2
2
4
4
6
4


3. feladat: Zárnyitogató (12 pont) /tesztadatok/

Egy zár három körlemez tárcsából áll (A, B és C), amelyek közös tengely körül forgathatók. Az egyes tárcsákon körben az 1,..,N egész számok vannak felírva. A tárcsák külön-külön és együtt is forgathatók mindkét irányban. Tehát a zárat háromféleképpen fordíthatjuk el: egyszerre egy tárcsát (A, B vagy C), bármely kettő tárcsát egyszerre (egy irányban) (AB, vagy AC vagy BC), ill. a három tárcsát egyszerre (ABC) forgatva egy irányba.

Egy lépésnek a fenti forgatások valamelyikét nevezzük, tetszőleges irányba egy egység elfordulással.

Feladat:

Készíts programot (ZAR.PAS vagy ZAR.C), amely a zár egy adott kiinduló helyzetéből ([a;b;c]) megadja a legrövidebb forgatási sorozat hosszát, amivel az [1;1;1] pozícióba juthatunk!
Bemenet:
A ZAR.BE állomány első sorában van az (1<=N<=100) érték. A második sorban három szám van, egy-egy szóközzel elválasztva, a három tárcsán pillanatnyilag beállított szám.
Kimenet:
A ZAR.KI állományba a legrövidebb lépéssorozat hosszát kell írni, amellyel a zár kinyitható, azaz az [1;1;1] pozícióba hozható.


Példa:

ZAR.BE ZAR.KI

1 5 3
4


4. feladat: Lift (21 pont) /tesztadatok/
Egy sokemeletes házban szokatlan módon üzemeltetik a liftet. A lift az első szintről indult és mindig felmegy a legfelső szintre, majd visszatér az első szintre. Menet közben megáll minden olyan szinten, amelyik úticélja valamelyik liftben tartózkodó utasnak. Hasonlóan olyan szinten is megáll, ahonnan utazni szándékozik valaki az aktuális irányban, feltéve, hogy még befér a liftbe (figyelembe véve az adott szinten kiszállókat).

Feladat:

Készíts programot (LIFT.PAS vagy LIFT.C), amely kiszámítja, hogy legkevesebb hány menet szükséges ahhoz, hogy minden várakozó embert elszállítson a lift.
Bemenet:
A LIFT.BE bemeneti állomány első sorában két szám van, N és K. N az épület szintjeinek (2<=N<=100) száma, K (1<=K<=10) pedig a lift kapacitása. A további N sor tartalmazza az egyes szinteken várakozó emberek adatait. Az állomány i-edik sorában azoknak a szinteknek a sorszáma van felsorolva, ahová az i-1–edik szintről utazni akarnak. A felsorolást minden sorban egy 0 szám zárja. Minden sorban legfeljebb 200 szám lehet.
Kimenet:
A LIFT.KI állomány egyetlen sort tartalmazzon, a legkevesebb menetek számát, amely az emberek elszállításához szükséges!
Példa:
LIFT.BE LIFT.KI
6 2 
2 3 2 0
1 3 0
1 2 0
2 5 0
3 6 2 0
1 2 3 0
3


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