Nemes Tihamér OKSzTV'97

1. feladat: Sereg (16 pont) /tesztadatok/

Burkusországban különös elven működik a hadsereg. Minden katonának 10 arany a zsoldja évente, plusz még annyi, ahány (nem csak közvetlen) beosztottja van. A sereg zsoldját a főparancsnok veszi át a királytól. A saját részét megtartja, a többit egy nap múlva adja tovább közvetlen alárendeltjeinek. ők is hasonlóan cselekszenek: a saját részüket megtartják, a többit újabb egy nap múlva adják tovább közvetlen alárendeltjeiknek s.í.t.

Az első év elején a sereg mindössze a leendő főparancsnokból áll.

A SEREGx.BE állomány 1. sorában a belépők száma (N<=100), a vizsgált időszak hossza (H) években, valamint a főparancsnok neve van, szóközzel elválasztva. A következő 3*N sorban a belépés sorrendjében a belépési év sorszámát (1-től kezdve), a belépő és közvetlen parancsnoka nevét adjuk meg.

Készíts programot, amely meghatározza, hogy H éven keresztül évente

A.

mennyi zsoldot fizet a király a seregnek,
B.
hány olyan katona van, akinek nincsen alárendeltje,
C.
kinek van a legtöbb közvetlen alárendeltje (ha több ilyen van, akkor csak egyet kell megadni),
D.
hányadik napon ér véget a zsoldosztás.
A SEREGx.KI állományba és a képernyőre a fenti 4 kérdésre adott válaszokat szóközzel elválasztva, H sorba kell kiírni; az i. sorba az i. évre vonatkozó választ.

Példa:
 

SEREGx.BE	SEREGx.KI
3 2 Tábornok 1 Ezredes Tábornok 1 Százados Ezredes 2 Kapitány Ezredes	33 1 Tábornok 3 45 2 Ezredes 3

2. feladat: Járda (16 pont) /tesztadatok/

Egy gyalogjárda két sorban négyzet alakú betonlapokkal van fedve. A járdalapokat mindkét sorban balról jobbra 1-től N-ig számozzuk. A törötteket ki kell cserélni. Mivel csak 2x1 méretű új lapok állnak rendelkezésre, szomszédos lapokat kell kicserélnünk. Sajnos, felszedés közben a hibátlan lapok is eltörnek, így tovább nem használhatók.

Készíts programot, amely kiszámítja, hogy legalább hány új 2x1-es lap kell a javításhoz.

A JARDAx.BE állomány első sorában a járda lapokban mért hossza (2<=N<=1000) van. A következő két-két sor a törött lapok darabszámát és sorszámát adja meg:

• a járda felső sorában:
• a törött lapok száma
• az egyes törött lapok sorszáma szóközzel elválasztva
• a járda alsó sorában:
• a törött lapok száma
• az egyes törött lapok sorszáma szóközzel elválasztva
A JARDAx.KI állományba és a képernyőre a javításhoz minimálisan szükséges 2x1-es lapok számát kell írni.

Példa:
 

JARDA1.BE	JARDA1.KI
10 5 2 3 4 9 10 6 1 4 5 6 8 9	6

3. feladat: Turista (19 pont) /tesztadatok/

Egy turista a turistaházból a lehető legrövidebb idő alatt szeretne eljutni a forráshoz. Útja hegyeken, völgyeken, szakadékokon vezet át. Minden út észak-déli vagy kelet-nyugati irányú. Előfordulhat, hogy a nagy szintkülönbség miatt kerülőt kell tennie. Segíts neki az útvonal megtervezésében!

Az úthálózat alkotta rácsot, ahol a rácspontok az útelágazások, egy NxM-es tömbbel ábrázoljuk; az egyes cellák értéke a domborzat adott rácspontban mért magassága. A turistaház a bal felső sarokban (az (1,1) koordinátájú pontban), a forrás a jobb alsó sarokban (az (N,M) koordinátájú pontban) található.

Egy útszakasz megtétele sík terepen egy percig tart. Minden méter szintkülönbség leküzdése további egy perccel növeli meg ezt az időt. Ha két pont szintkülönbsége nagyobb az előre megadott K értéknél, a turistának kerülőt kell tennie.

Írj programot, amely meghatározza a túra megtételéhez szükséges legrövidebb időt és az útvonal szakaszainak számát!

A HEGYx.BE állomány első sorában N, M és K értéke (1<=N<=100, 1<=M<=100) található, egy-egy szóközzel elválasztva. A következő N sor mindegyike M rácspont magasságát tartalmazza, szóközzel elválasztva.

A HEGYx.KI állományba és a képernyőre a túra megtételéhez szükséges legrövidebb időt és az útszakaszok számát kell írni. Ha nem lehet eljutni a célba, a program írja ki a NEM ÉR CÉLBA szöveget!

Példa: (vastagon szedve a túra útvonala)

4. feladat: F.I.L.E. (16 pont) /tesztadatok/

Az ábécé betűit 8x8-as pontmátrixban ábrázoljuk, '.'-tal kódoljuk a világos, és 'X'-szel a sötét pontokat. A vonalak belsejében levő sötét pontoknak legfeljebb 2 sötét szomszédja lehet, a vonalak találkozásánál levőknek 3, a vonalak végén levőknek pedig 1. A betűk tetszőleges állásúak lehetnek (pl. normál, ferde, oldalra döntött, fejre állított), és a felismerhetőség határán belül a méretük is különbözhet (pl. az I betű állhat 8 pontból, de akár 4-ből is).

Az I betű egyenes és döntött, az F fordított állásban látható az ábrán.

A BETUKx.BE állomány első sorában a betűk száma (N), a következő N*8 sorban pedig az egyes betűk pontmátrixa, soronként 8 karakter ('X' vagy '.') van. Az állományban csak a következő nagybetűk fordulnak elő:

BDEFHILOY.
Készíts programot, amely a bemeneti állományból ­ a vonalak száma és találkozásaik jellege alapján ­ felismeri az F, I, L, E betűket! A BETUKx.KI állományba és a képernyőre egyetlen sorba (a bemenő állomány sorrendjében) ki kell írni a felismert betűket. A fel nem ismert betűk helyére a - karakter írandó.

Példa:
 

BETUK1.BE	BETUK1.KI
2 ........ ........ ........ ........ .XXXXX.. ........ ........ ........ ........ .X.....X ..X...X. ...X.X.. ....X... ....X... ....X... ........	I-  mert az Y-t a programnak  nem kell felismernie