Nemes Tihamér OKSzTV'2001

1. feladat: Jégtömb (20 pont) /tesztadatok/

Jégtömböt írunk le egy táblázat segítségével. A szürkével jelölt (számozott) pontok jelölik a jégtömbhöz tartozó pozíciókat. Ha a jégtömbre meleg levegőt fújunk, akkor a szélén olvadni kezd, s a keletkezett víz elfolyik.

Az olvadás szabálya: egy időegység alatt abban a mezőben levő jég olvad el, amelynek 4 oldalszomszédja közül legalább kettőben levegő volt. (Ilyenek az ábrán az 1-es számmal jelölt mezők.) Ennek eredményeképpen keletkezhetnek újabb ilyen tulajdonságú mezők (az ábrán 2-vel jelöljük őket), amelyek makd a 2. időegységben olvadnak el, és így tovább.

Feladat:

Készíts programot, (JEGTOMB.PAS vagy JEGTOMB.C), amely egy adott jégtömbre megadja, hogy hány időegység alatt olvad el teljesen, illetve időegységenként megadja, hogy a jégtömb még hány mezőből áll!

Bemenet:

A JEGTOMB.BE állomány első sorában két egész szám van, egyetlen szóközzel elválasztva, a táblázat sorainak (1<=N<=100) és oszlopainak (1<=M<=100) a száma. S következő N sor mindegyike M számjegyet tartalmaz, közülük az i-edik sor j-edik számjegye 0, ha a táblázat i-edik sorának j-edik oszlopában levegő van, és 1, ha jég. A táblázat szélső soraiban és oszlopaiban biztosan levegő van.

Kimenet:

A JEGTOMB.KI állomány első sorába azon időegységek T számát kell írni, amelyek elteltével a jégtömb teljesen elolvad. A következő T sorba egy-egy számot kell írni, közülük az i-edik a jéggel teli mezők száma legyen az i-edik időegység kezdetén! (A legutolsó időegység után már 0 a jéggel teli mezők száma, ezt az állományba nem szabad kiírni.)

Példa:

(Az ábrán látható jégtömbre.)

2. feladat: Licit (20 pont) /tesztadatok/

Nevesincs város polgármestere elhatározta, hogy értékesíti a város mellett levő téglalap alakú földdarabot. A földet egyforma méretű parcellákra osztotta.

A polgármester úgy döntött, hogy a parcellákat nyilvános pályázat keretében adja el, azaz egy adott határidőig minden érdeklődő lezárt borítékban leadhatja ajánlatát. Egy pályázó csak egy ajánlatot nyújthat be, amelyben meg kell adnia, hogy melyik parcellától melyik parcelláig terjedő részt kívánja megvenni, és mennyiért.

A pályázat sikeres volt, a határidő lejártáig N pályázat érkezett. Ezek közül ki kell választani azokat az ajánlatokat, amelyek a legtöbb bevételt eredményezik, s persze úgy, hogy egyetlen parcellát sem ítélnek oda egynél több pályázónak. Egy-egy pályázó vagy az összes kért parcellát megkapja, vagy egyet sem kap meg. Előfordulhat, hogy a maximális bevétel eléréséhez nem kell eladni az összes parcellát.

Feladat:

Írj programot (LICIT.PAS vagy LICIT.C), amely megadja a választ a polgármester problémájára!

Bemenet:

A LICIT.BE állomány első sorában a pályázatok N száma (1<=N<=100) és a parcellák M száma (1<=M<=100) található, egy szóközzel elválasztva. A következő N sor az egyes pályázók adatait tartalmazza, a pályázókat ez a sorrend azonosítja. Mindegyik 3 számot tartalmaz egy-egy szóközzel elválasztva: A B FT, ami azt jelenti, hogy a pályázó az A sorszámú parcellától (1<=A<=M) a B sorszámú parcelláig (A<=B<=M) terjedő részért FT forintot fizetne (1000<=FT<=1000000).

Kimenet:

A LICT.KI állomány első sorába az elérhető legnagyobb bevételt kell írni. A második sorba a nyertes páláyzók sorszámai kerüljenek egy-egy szóközzel elválasztva. Ha több megoldás is van, csak egyet kell kiírni (bármelyiket).

Példa:

3. feladat: Térkép (20 pont) /tesztadatok/

Újlandia térképének (N sorból, M oszlopból álló téglalap) K darab téglalap alakú részéről készítünk nagyításokat. A téglalapok oldalai párhuzamosak a térkép oldalaival, s mindegyiket a bal felső és a jobb alsó sarkának koordinátáival adjuk meg. Az egyes téglalapok átfedhetik egymást. (Minden koordináta 1 blokkot jelöl meg a térképen, azaz az (1,1) és (1,1) koordinátákkal megadott téglalap kerülete 4, területe 1 egység. A teljes térkép területe N*M, kerülete pedig 2*N+2*M egység.)

Feladat:

Készíts programot (TERKEP.PAS vagy TERKEP.C) a nagyított részek együttes kerületének és területének meghatározására!

Bemenet:

A TERKEP.BE állomány első sorában N (1<=N<=160), M(1<=M<=400) és K (1<=K<=100) értéke van, egy-egy szóközzel elválasztva. A következő K sorban az egyes téglalapok leírása következik. Mindegyik sor 4 egész számot tartalmaz, a téglalap bal felső (1<=BFY<=N, 1<=BFX<=M) és jobb alsó (BFY<=JAY<=N, BFX<=JAX<=M) sarkának koordinátái. A koordinátát tehát (sor, oszlop) párként adjuk meg.

Kimenet:

A TERKEP.KI állomány egyetlen sorába a nagyított rész együttes kerületét és területét kell írni, egyetlen szóközzel elválasztva.

Példa:

4. feladat: Jelek (15 pont) /tesztadatok/

A csillagászok naponta észlelnek távoli égitestekről érkező jelsorozatokat. Minden jelsorozat egy-egy bitsorozattal azonosítható. Megfigyelték, hogy az A és a B égitestről érkező jelek nagyon szabályosak.

Az A égitest esetén:

A1. A 0 és a 01 két észlelt jelsorozat.
A2. Ha az U észlelt jelsorozat, akkor az U0U1 és az U1U0 is észlelt jelsorozat.
A3. Minden észlelt jelsorozat megkapható az A1 és az A2 szabályok véges számú többszöri alkalmazásával.

A B égitest esetén:

B1. A 01 egy észlelt jelsorozat
B2. Ha az U észlelt jelsorozat, akkor 0U1 is észlelt jelsorozat.
B3. Ha az U és a V észlelt jelsorozatok, akkor az UV is észlelt jelsorozat.
B4. Minden észlelt jelsorozat megkapható a B1, B2 és B3 szabályok véges számú többszöri alkalmazásával.

Feladat:

Készíts programot (JELEK.PAS vagy JELEK.C), amely meghatározza, hogy a vizsgált jelsorozatok melyik égitestről érkezhettek.

Bemenet:

A JELEK.BE szöveges állomány első sorában a vizsgálandó jelsorozatok N (1<=N<=100) száma van. A következő N sor mindegyikében egy-egy jelsorozat van, amelynek hossza nem nagyobb, mint 255, és csak a 0 és 1 karaktereket tartalmazhatja.

Kimenet:

A JELEK.KI szöveges állományba pontosan N sort kell írni. Az i-edik sor tartalma az i-edik vizsgált jelsorozathoz tartozó válasz, amely egy vagy két karakterből álló szöveg:

A, ha a jelsorozat csak az A égitestről érkezhetett,
B, ha a jelsorozat csak a B égitestről érkezhetett,
AB, ha a jelsorozat az A és a B égitestről egyaránt érkezhetett,
C, ha a jelsorozat sem az A, sem a B égitestről nem érkezhetett.

Példa:

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