A KöMaL 2015. májusi informatika feladatai

I-jelű feladatok A beküldési határidő 2015. június 10-én LEJÁRT.

---

I. 376. A keresztrejtvényfejtés széles körben elterjedt népszerű játék. Sok változatát fejlesztették ki. A hagyományos változatban a szavak elválasztására fekete mezők szolgálnak. A megfejtésekkel az üres mezők vízszintesen balról jobbra, illetve függőlegesen felülről lefelé tölthetők ki. A mezők számozása a bal felső sarokból indul, ahol a vízszintes vagy függőleges megoldás szava kezdődik. Minden olyan mező számot kap, ahol vízszintesen vagy függőlegesen megfejtés kezdődik. A feladatban szereplő keresztrejtvények egybetűs szavakat nem tartalmaznak. Ha egy mező vízszintes és függőleges szó első betűjét is tartalmazza, akkor csak egy számot kap.

Keresztrejtvény hálója és számozása:

A feladatok megoldásának teszteléséhez rendelkezésünkre áll egy, a honlapunkról letölthető halo.txt fájl, amelyben egy \(\displaystyle N\times M\) (\(\displaystyle 5\le N, M\le 15\)) méretű keresztrejtvény hálója van leírva. Az állomány első sorában \(\displaystyle N\) és \(\displaystyle M\) értéke szerepel szóközzel elválasztva, majd a következő \(\displaystyle N\) sor a mezők állapotát tartalmazza. A fekete mezőket ,,f'', az üreseket ,,.'' karakter ábrázolja.

Készítsünk programot i376 néven, amely az alábbi problémákat oldja meg:

Minden képernyőre írást igénylő részfeladat megoldása előtt írjuk ki a feladat sorszámát. Ha a felhasználótól kérünk be adatot, jelenítsük meg a képernyőn, hogy milyen értéket várunk (például a 4. feladat esetén: ,,4. feladat - Adjunk meg egy mezőt: ''). Az ékezetmentes kiírás is elfogadott.

1. Olvassuk be a halo.txt állományban talált adatokat, és azok felhasználásával oldjuk meg a következő feladatokat.

2. Írjuk ki a képernyőre, hogy a keresztrejtvény hálójában hány fekete és hány üres mező van.

3. Határozzuk meg azt a sort, illetve azt az oszlopot, amelyben a legtöbb fekete mező van. Ha több ilyen van, akkor a legkisebb sorszámút írassuk ki a képernyőre.

4. Kérjük be a felhasználótól a keresztrejtvény egy mezőjének koordinátáját (például: 10h) és írjuk ki, hogy be kell-e majd számozni.

5. Írjuk ki a képernyőre, hogy a keresztrejtvény hálójában vízszintesen hány \(\displaystyle 2, 3, \dots, 10\) betűs szó helyezhető el.

6. A szabályoknak megfelelően számozzuk be a keresztrejtvény mezőit és írjuk az eredményt a szamozott.txt állományba. A mezők tartalmát 3 karakternyi helyre írjuk ki.

7. Írassuk ki, hogy a keresztrejtvénybe írandó szavakhoz hány vízszintes és hány függőleges meghatározás tartozik.

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

Letölthető fájl: halo.txt

(10 pont)

megoldás, statisztika

---

I. 377. Az oktatas.hu portál évről évre megjeleníti a tantárgyi OKTV döntők eredményét:

http://www.oktatas.hu/kozneveles/tanulmanyi_versenyek/oktv_kereteben/dijazottak_eredmenyek

Az eredménylistát PDF formátumú dokumentumként adják meg tantárgyanként. A formátum módot ad ugyan arra, hogy egyszerű szöveges keresést végezzünk, de összetett keresést vagy statisztikai feldolgozást nem támogat.

A portál üzemeltetőitől azt a feladatot kaptuk, hogy tervezzünk adatbázist az eredmények tárolására és tervezzük meg azt a folyamatot, amely során az adatok átvihetők a fájlokból az adatbázisba. Teszt céllal az informatika tárgy alkalmazói kategóriája utolsó öt évének adatait kell a megtervezett adatbázisba betöltenünk.

A megoldáshoz csak a fenti címen elérhető fájlokat használhatjuk. A szükséges konverziós lépésekhez tetszőleges - lehetőleg ingyenes - programot igénybe vehetünk.

Az üzemeltetők kikötötték, hogy az adatbázist a Microsoft Access alapértelmezett formátumában vagy MySQL dump fájlként kell leadni, mivel a hétköznapokban ezeket az eszközöket használják.

Beküldendő egy tömörített állományban (i377.zip) a megoldás leírása (i377.pdf) és az adatbázis (i377.accdb, i377.sql). A leírás tartalmazza az adatbázis modelljét (a táblák kapcsolatát) kifejező képet, a használt adatbázis-kezelő nevét és verzióját, valamint a PDF fájlok feldolgozásának reprodukálható folyamatát, a közben felvetődő technikai vagy tartalmi jellegű problémákat és azok megoldását is.

(10 pont)

megoldás, statisztika

---

I. 378. Adott egy \(\displaystyle N\times M\) pixelből álló fekete-fehér kép, amelyet táblázatos elrendezésben 0 és 1 számokkal írunk le. Egy ilyen képet akkor tekintünk szépnek, ha az élszomszédos mezők közül minél több azonos. Célunk az eredeti kép szebbé alakítása bizonyos pixelek értékének megcserélésével. Egy képpont cseréje \(\displaystyle Q\) forintba kerül. Az átalakított kép szépségét úgy vesszük figyelembe, hogy minden élszomszédos, különböző színű pixelpár további \(\displaystyle P\) forint ,,költséget'' jelent. Keressük meg néhány adott képre azt az átalakítást, amely mellett a lehető legkisebb a \(\displaystyle P+Q\) költség.

Programot nem kell beküldeni, egyedül a három, honlapunkról letölthető (in.1, in.2, in.3) képre kell három kimenetet adni (out.1, out.2, out.3). A bemenet első sorában négy egész szám áll: \(\displaystyle N\), \(\displaystyle M\), \(\displaystyle P\), \(\displaystyle Q\) -- a táblázat sorainak, oszlopainak száma, illetve a két költséget leíró paraméter. Ezután \(\displaystyle N\) sor következik, mindegyikben \(\displaystyle M\) karakter: a fénykép. A kimenet szintén egy \(\displaystyle N\times M\)-es táblázat a bemenethez hasonló formában. A feladatra nem feltétlenül kell optimális megoldást adni, mivel a feladat beküldői egymással versenyeznek: az kap 10 pontot, akinek a három bemenetre összesen a legkisebb a \(\displaystyle P+Q\) költség, a többiek arányosan kevesebbet. Például a következő kép esetén:

egy lehetséges (nem feltétlenül optimális) átalakítás:

Itt \(\displaystyle 6\cdot 2+3\cdot 3 =21\) forint a költség.

Beküldendő a három átalakított fénykép egy tömörített (i378.zip) állományban.

Letöltendő állományok: in.1, in.2, in.3.

(10 pont)

megoldás, statisztika

S-jelű feladatok A beküldési határidő 2015. június 17-én LEJÁRT.

---

S. 99. Egy \(\displaystyle M\) (\(\displaystyle 1\le M\le 100\;000\), \(\displaystyle M\) egész szám) hosszú falon \(\displaystyle N\) (\(\displaystyle 1\le N\le 5000\)) repedés keletkezett. Az egyszerűség kedvéért a repedéseket mint pontokat képzeljük el a falon, helyüket a fal egyik végétől valamilyen \(\displaystyle x\) (\(\displaystyle 1\le x\le M\), egész) koordináták adják meg. Célunk az, hogy lefessük a fal minden repedését. Úgy festünk, hogy kinyitunk egy \(\displaystyle w\) feliratú doboz festéket, amely pontosan \(\displaystyle w\) hosszú falrész festésére alkalmas, majd a tartalmával lefestünk egy \(\displaystyle x_0\) és \(\displaystyle x_1\) koordinátákkal határolt falrészt (\(\displaystyle w=x_1-x_0+1\)). A kiválasztott tartományon belül természetesen lefestjük az ép falrészeket is -- akár többször is. Addig nyitunk ki újabb festékesdobozt és festünk, amíg minden repedést el nem tüntettünk. A festéshez minden \(\displaystyle w\) (\(\displaystyle 1\le w\le M\)) egész számra egy \(\displaystyle w\) feliratú, és ismert \(\displaystyle b_j\) árú doboz festék áll rendelkezésre. Egy hosszabb festés nem feltétlenül drágább, mint egy rövidebb, sőt egy nagyobb doboz festék ára lehet egy kisebb doboz festék árával egyenlő, vagy annál kisebb is. Fessük le a lehető legolcsóbban az összes repedést a falon. Ehhez egy típusú festékből akár többet is felhasználhatunk.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et, majd a következő \(\displaystyle N\) sorból az \(\displaystyle a_i\) egészeket, azaz a repedések helyét. A következő \(\displaystyle M\) sorban rendre az egyes hosszokhoz tartozó festékes dobozok \(\displaystyle b_j\) ára szerepel. Írjuk a standard output első sorába a minimális pénzt, amennyiből a festés megoldható. Helytakarékosság miatt a bemenetben az \(\displaystyle N\), illetve az \(\displaystyle M\) sorban lévő számokat / jellel elválasztva egy sorba írtuk.

Magyarázat: ha veszünk egy 4, egy 1 és egy 2 feliratú vödröt, akkor azokkal pont le tudjuk festeni az összes repedést. Az ár: \(\displaystyle 4+2+3=9\).

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s99.zip állományban a program forráskódja (s99.pas, s99.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s99.txt, s99.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

megoldás, statisztika