Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A KöMaL 2009. áprilisi informatika feladatai

Kérjük, ha még nem tetted meg, olvasd el a versenykiírást.


Feladat típusok elrejtése/megmutatása:


I-jelű feladatok

A beküldési határidő 2009. május 15-én LEJÁRT.


I. 211. A képen látható objektumok szerkezetének egyszerűsítésére a vázkijelölés módszerét alkalmazhatjuk. Ennek alapötlete, hogy az objektumot annak egy pixel vastag ,,középvonalával'' helyettesítjük. Így az objektumok kevesebb információval leírhatók és a kapott vázak az objektumok összehasonlítására alkalmazhatók például a karakterfelismerésben.

Olvassunk be egy fekete-fehér képet, majd a fekete alakzatok vázát vékonyítási módszerrel határozzuk meg és jelenítsük meg. A vékonyítási módszertől azt várjuk el, hogy végpontot ne töröljön, őrizze meg az alakzatok összefüggőségét és egy pixel vastag vázat határozzon meg.

Algoritmus: Rendeljünk a fekete színhez 1 és a fehér színhez 0 értéket. A vékonyítás során az alakzat kontúrpontjain történhet változás, azaz az olyan 1 értékű pontokon, amelyeknek 8-környezetében van legalább egy 0 érték. A szomszéd pontokat a következőképpen jelöljük:

Első lépés: Az s0 pontot töröljük, ha a következő négy feltétel mindegyike teljesül:

A Szomszédszám (s0) az s0 pont 1 értékű szomszédjainak száma. Az Átmenet (s0) pedig a 0-1 átmenetek száma az s1,s2,...,s7,s8,s1 sorozatban.

Például:

Második lépés: Az i. és ii. feltétel ugyanaz, de az iii. és az iv. helyett az

feltételek teljesülése esetén töröljük a pontokat.

Az első lépésben az alakzat összes szélső pontját megvizsgáljuk és törlésre kijelöljük a négy feltételnek eleget tevő pontokat. A törlést a teljes átvizsgálás után hajtjuk végre. Ezután a második lépésben a feltételek második változatával jelöljük meg a törlendő pontokat. Majd ebben az esetben is a teljes kép elemzése után hajtjuk végre a törlést.

A váz meghatározásához a két lépést addig folytatjuk, amíg már nem tapasztalunk változást.

Készítsünk programot, amely a bemeneti adatállományban megadott fekete-fehér BMP kép vázát meghatározza és az eredeti képpel együtt a képernyőn megjeleníti. A program parancssori argumentuma legyen a képállomány neve. Más, eltérő képtípust is használhatunk, például RAW állományt, de akkor a program parancssori argumentuma a kép függőleges, vízszintes mérete és a képállomány neve legyen.

Beküldendő a program forráskódja (i211.pas, i211.cpp, ...), valamint a program rövid dokumentációja (i211.txt, i211.pdf, ...). A dokumentáció tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztőkörnyezetben fordítható és hogyan paraméterezhető.

(10 pont)

megoldás, statisztika


I. 212. A 8×8 sakkegyesület rapidsakk versenyein legfeljebb 8 versenyző vesz részt. A versenyen mindenki mindenkivel kétszer méri össze az erejét, egyszer a világos és egyszer a sötét bábukat vezetve. Egy partin a győztes 1, a vesztes 0 pontot kap, és döntetlen esetén mindketten 0,5-0,5 ponttal lesznek gazdagabbak.

A verseny adatait táblázatkezelő program segítségével tartják nyilván. Az eredményeket a parti nevű munkalapra a világos bábukat vezető szempontjából jegyzik be. Ha C vezette a világos, A pedig a sötét bábukat és C nyert, akkor C sorába és A oszlopába az 1 érték kerül.

Oldjuk meg, hogy a parti munkalapon az eredmények területére csak a 0, 0,5, 1 értékeket lehessen bevinni. Az első oszlopba kell beírni a versenyzők nevét, az első sor pedig automatikusan kerüljön kitöltésre az első oszlop adatai alapján. (A nem létező versenyzők sorában és oszlopában nem kell megakadályozni az eredménybejegyzést.)

Az aktuális nevű munkalapra készítsük el a verseny pillanatnyi állását. A versenyzők sorrendjét a szerzett pontok száma szabja meg, a nagyobb pontszámú versenyző kerül előbbre. Az azonos pontszámmal rendelkezők tetszőleges sorrendben feltüntethetőek, de helyezésüknek egyezniük kell.

Beküldendő a táblázatkezelő munkafüzet (i212.xls, i212.ods, ...), illetve egy rövid dokumentáció (i212.txt, i212.pdf, ...), amelyben szerepel a megoldáskor alkalmazott táblázatkezelő neve, verziója, valamint a megoldás rövid leírása.

(10 pont)

megoldás, statisztika


I. 213. ,,Éves kimutatás'' - áll a furcsa papírlap tetején. Alatta pontokba szedve három utasítás olvasható, melyeket egy táblázat követ: első oszlopa egytől kezdve be van számozva, második oszlopában furcsa szavak, harmadik oszlopában pedig ismét számok találhatók.

Poirot úr egészen biztos benne, hogy a bravúros nyomozás eredményeképp tegnap letartoztatott, egyébként egy neves vállalatot vezető Colston úr dolgozószobájában talált irat nem a gyanúsított ,,elsődleges'' tevékenységével kapcsolatos.

Bízva algoritmuselméleti és kódfejtői jártasságunkban, a nyomozó minket kért meg, hogy a papírlapot, amely szerinte a vállalatvezető által titokban irányított bűnszervezet hierarchiáját írja le, dekódoljuk. Segítségként elárulta, hogy egy ilyen szervezetben - a vezetőn kívül - mindenkinek pontosan egy felettese van, a papírlapon szereplő utasításokat vélhetőleg - saját érdekében - mindenki betartotta, illetve a listán valószínűleg szerepel Ms. Hartsell, a vállalatvezető titkárnője is.

A furcsa papírlap letölthető honlapunkról (i213.doc). A hierarchia megfejtése 5, a nevek dekódolása további 5 pontot ér. A megfejtés minden sorában pontosan egy név szerepeljen, egy tag beosztottjait pedig jelöljük úgy, hogy egy szinttel beljebb tabuláljuk. Beküldendő a megfejtés egyszerű szöveg formában (i213.txt), a megfejtés menetének rövid leírása (i213mo.txt, i213mo.pdf, ...), illetve a megfejtéshez esetlegesen használt saját készítésű program(ok) forráskódja.

(10 pont)

statisztika


S-jelű feladatok

A beküldési határidő 2009. május 15-én LEJÁRT.


S. 44. Bergengóciában minden évben megrendezésre kerül a Nemzeti Villamoshajtó Bajnokság, a királyság legnevesebb versenysorozata. Ennek keretében minden nagyváros egy-egy versenyt rendez, melynek helyszíne a város leghosszabb villamospályája. A versenyzők egyesével indulnak, céljuk, hogy a lehető legrövidebb idő alatt végighaladjanak a pályán.

Bár a verseny ideje alatt az utasszállítás szünetel, a teljes közúti forgalmat még egy ekkora attrakció kedvéért sem lehet leállítani. A szörnyű balesetek elkerülése érdekében ezért a versenyzők a kereszteződéseknél a piros jelzésen a verseny során sem haladhatnak át.

Írjunk programot, mely meghatározza, hogy optimális esetben mennyi idő alatt teljesíthető a teljes táv. A program a pálya leírását fájlból olvassa, az eredményt fájlba írja. A bemeneti, illetve kimeneti fájlok nevei az első, illetve második parancssori argumentumok.

A villamos eleje az x=0 koordinátájú pontból indul a t=0 időpillanatban, és minden időegység kezdetén -1, 0, +1 egységgel változtathatja (pillanatszerűen) a sebességét, mellyel ezután egységnyi ideig egyenletesen halad az x tengely mentén. A villamos megállhat, de nem tolathat és nem is lépheti túl az M maximális sebességet.

A kereszteződéseknél a villamos elejének kell a zöld jelzésen áthaladni, a lámpa állapotaihoz balról nyílt, jobbról zárt időintervallumok tartoznak. (Tehát az éppen pirosra váltó lámpán a villamos még áthaladhat, de az éppen zöldre váltón még nem.) Célba érkezésnek azt a pillanatot tekintjük, amikor a villamos elejének x koordinátája megegyezik a pálya L hosszával.

A bemenet első sorában három, szóközzel elválasztott szám szerepel: a pálya 10\leL\le5000 hossza, a lámpák 0\leN\le1000 száma, illetve a villamos 1\leM\le30 végsebessége. Az ezt követő N db sor mindegyikében egy-egy lámpa leírása következik: a lámpa 1\leXi\leL pozíciója, állapotváltásainak 1\leCi\le100 száma (de összesen legfeljebb 1000 állapotváltás), majd Ci db szám, az egyes piros-zöld állapotváltások 0\le T_{i,j} \le
10\;000 időpontja, mind szóközzel elválasztva. Kezdetben minden lámpa zöld jelzést mutat.

A kimenetben egyetlen szám szerepeljen: a teljes táv megtételéhez minimálisan szükséges idő egészrész-törtrész alakban (a \ b/c), ahol c a célba érkezés sebessége.

A maximális pontszám eléréséhez a programnak a legnagyobb tesztesetekre is néhány percen belül le kell futnia (egy korszerű PC-n). A feladat 64kB memóriában is megoldható, ezért az időkorlát az ilyen környezetekben készült megoldásokra is vonatkozik, így (átmeneti) segédfájlok használatát ott sem javasoljuk.

Beküldendő a program forráskódja (s44.pas, s44.cpp, ...), valamint a program rövid dokumentációja (s44.txt, s44.pdf, ...). A dokumentáció tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztőkörnyezetben fordítható és hogyan paraméterezhető.

Figyelem: A feladat szövege az "áthaladás" szót használja a villamos és a kereszteződések (lámpák) viszonyának leírásához, mely álló villamos esetén nehezen értelmezhető. Ezekben az esetekben tekintsük úgy, hogy a villamos az egy helyben állás teljes időtartama alatt, a végpontokat is beleértve, minden pillanatban "áthalad" a kereszteződésen.

(10 pont)

megoldás, statisztika


Figyelem!

Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.