A KöMaL 2014. novemberi 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ű feladatokA beküldési határidő 2014. december 10-én LEJÁRT. |
I. 358. Az aknakereső játék célja az \(\displaystyle N\times N\) (\(\displaystyle 2\le N\le 50\)) négyzet alakú mezőn lévő \(\displaystyle K\) (\(\displaystyle 0\le K\le N\times N/2\)) akna megtalálása, illetve azok elkerülése. A cellák tartalma eredetileg el van rejtve, de ha kiválasztjuk, akkor megismerjük a tartalmát. Ha a cellában akna volt, akkor vége van a játéknak, különben egy 0 és 8 közötti szám jelenik meg. A szám azt adja meg, hogy hány akna van a választott cella nyolc szomszédjában összesen.
Ha a felfedett cella szomszédságában nincs akna, akkor az összes szomszédja is felfedetté válik, és ez rekurzívan folytatódik a szomszédok szomszédjaival is. Győzelemmel akkor fejeződik be a játék, ha felfedtünk minden olyan mezőt, amely alatt nincs akna.
A következő példában egy játék egy lépését láthatjuk:
Készítsünk programot i358 néven, amely az aknamezőt előállítja és a felhasználóval a játékot levezeti.
1. Olvassuk be \(\displaystyle N\) és \(\displaystyle K\) értékét, és azok felhasználásával oldjuk meg a következő feladatokat.
2. Állítsuk elő a játék pályáját, amelyen véletlenszerű cellákban \(\displaystyle K\) darab akna legyen. ,,*'' jelöli az aknát és ,,.'' az üres cellát.
3. Programunk kipróbálása, tesztelése miatt állítsuk be, hogy Teszt és Játék üzemmódból választani lehessen. A Teszt üzemmódban az aknák látszódjanak, míg a Játék-ban maradjanak rejtve.
4. Olvassuk be a pálya egy sor és oszlop koordinátáját és a cella tartalma alapján jelenítsük meg a választ.
\(\displaystyle a)\) Ha a cellában akna volt, akkor írjuk ki, Bumm! és a program álljon le.
\(\displaystyle b)\) Amennyiben a cellában nem volt akna, akkor jelenítsük meg a pályán a szabályok szerinti eddigi információkat a felfedett és a még nem ismert cellákkal.
5. Folytassuk a tippek beolvasását addig, amíg az összes üres cella szomszédjainak számát a felhasználó meg nem határozza a játékkal. Ha ez sikerül, akkor abban az esetben írjuk ki, hogy Nyertél!
6. Minden tippelés előtt jelenítsük meg, hogy még hány fel nem derített üres cella van a pályán és hányadik tippelés következik éppen.
Beküldendő egy tömörített i358.zip állományban a program forráskódja (i358.pas, i358.cpp, ...) és rövid dokumentációja (i358.txt, i358.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.
(10 pont)
I. 359. Az alábbiakban egy teniszmérkőzés adatait kell feldolgoznunk. A teniszmérkőzés eredményét és pillanatnyi állását az alábbiak szerint számítják:
1. Egy mérkőzés akkor ér véget, ha valamelyik játékos legalább három játszmát nyer.
2. Egy játszma megnyeréséhez legalább 6 játékot kell nyerni úgy, hogy az ellenfél legfeljebb kettővel kevesebb játékot nyer. (Tehát egy játszma nyerhető például 6:1, 6:4, 7:5 vagy 11:9 arányban, de nem nyerhető 6:5-re vagy 7:6-ra, azaz ,,rövidítés'' nincs.)
3. Egy játékot az a játékos nyer, aki legalább 4 labdamenetet megnyer úgy, hogy az ellenfél legfeljebb kettővel kevesebb megnyeréséig jut.
4. A labdamenetet a feladatban úgy definiáljuk, hogy azt minden esetben megnyeri az adogató (A) vagy a fogadó (F) játékos.
A feladat megoldásához lényeges, hogy a mérkőzés az első játékos adogatásával kezdődik, egy játékon belül ugyanaz a játékos adogat, a következő játékban a másik játékos adogatása következik a mérkőzés állásától függetlenül.
Egy munkafüzet labdamenetek munkalapjának első oszlopában rögzítjük a mérkőzés egy adott állásáig, hogy az adott labdamenetet az adogató (A) vagy a fogadó (F) játékos nyerte-e. A labdamenetek száma legfeljebb 1000 lehet, és a munkalap \(\displaystyle n\)-edik sorbán álló A betű azt jelenti, hogy az \(\displaystyle n\)-edik lejátszott labdamenetet az adogató nyerte. A mérkőzés végét követően újabb labdamenetet már nem rögzítünk, vagyis egy teljes mérkőzés után az utolsó labdamenet nyertesének betűjele alatti cellák üresek.
Az állás munkalapon tüntessük fel a pillanatnyi - a labdamenetek munkalap utolsó kitöltött sorának megfelelő - állást, amely tartalmazza a megnyert játszmák állását, a korábbi játszmák eredményét és adott játszmán belül a megnyert játékok állását, valamint adott játékon belül az állást. Az első sorban a táblázat fejlécét hozzuk létre a fenti leírásnak megfelelően. A teljes pontszám csak úgy érhető el, ha a játékon belüli állás a teniszben szokásos módon kerül feltüntetésre.
A teszt munkalap első négy oszlopába vegyünk fel egy-egy olyan értéksorozatot, amelyet a labdamenetek munkalap első oszlopába illesztve az állás munkalap helyes eredményt ad.
A megoldásban saját függvény vagy makró nem, de a labdamenetek munkalapon a második oszloptól tetszőleges számú segédcella használható.
Példa az állás munkalap tartalmára:
Beküldendő egy tömörített i359.zip állományban a feladatban leírt tartalmú táblázat (i359.xls, i359.xlsx, i359.ods, ...) és rövid dokumentációja (i359.txt, i359.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja a használt táblázatkezelő nevét és verziószámát.
(10 pont)
I. 360. Ma már nem csak mosóport, koncertet és bulvárlapokat hirdetnek reklámok, hanem múzeumokat, oktatási intézményeket is.
Csatlakozzunk mi is ehhez a sorhoz és tervezzünk egy KöMaL reklámot, amelyet akár tömegközlekedési eszközök oldalán is el lehet helyezni. A terv minél valósághűbb bemutatására a reklámot helyezzük el a troli.jpg kép oldalára. (A kép forrása: http://iho.hu/img/galery/130523-iktroli.jpg.)
Az interneten fellelhető képeket nagyon sokan céltól függetlenül szabadon felhasználhatónak tekintik, gyakran még a forrást sem jelölik meg a felhasználás során. Emiatt gyakran alkalmaznak úgynevezett vízjelet, amely utal a készítőre. A vízjel lehet szöveges vagy grafikus. Az alábbi példa egy szöveges vízjelet mutat:
Tervezzünk vízjelet a lap számára, amelyet a komal.hu legalább \(\displaystyle 800\times 600\) méretű képein el lehet helyezni. A vízjel alkalmazását a http://www.komal.hu/hirek/2004-09/imo2004/beszamolo.h.shtml lapon szereplő képek valamelyikén kell bemutatnunk. A vízjel legyen jól felismerhető, de ne legyen zavaró.
A megoldást bármely ingyenes eszközzel elkészíthetjük.
Beküldendő a megoldás leírása (i360.pdf), amely tartalmazza a használt szoftver(ek) nevét és verzióját, valamint az elkészült reklám és vízjel adott képen való elhelyezésének reprodukálásához elegendő pontosságú leírását. A kész képeket egyetlen tömörített fájlban kell feltölteni (i360.zip).
(10 pont)
S-jelű feladatokA beküldési határidő 2014. december 10-én LEJÁRT. |
S. 93. Adott \(\displaystyle N\le 100\; 000\) sportoló, akik egy tréningen vesznek részt. Mindenkinek körbe kell bicikliznie egy tavat, majd rögtön utána át kell rajta evezni (oda-vissza), ebben a sorrendben. Sajnos az egyesület nem túl gazdag, ezért mindössze egyetlen bicikli, és egyetlen csónak áll rendelkezésükre. Így egyszerre legfeljebb egy ember biciklizhet, és egy evezhet. Tudják minden sportolóról, hogy hány órába telik körbebiciklizni, és hány órába telik átevezni a tavat. Szeretnék a tréninget mihamarabb befejezni, kérdés, hogy ez hány órát vesz összesen igénybe.
A program olvassa be a standard input első sorából \(\displaystyle N\)-et, majd a következő \(\displaystyle N\) sorból a \(\displaystyle b_i\), \(\displaystyle e_i\) szóközzel elválasztott óraszámokat, melyek a biciklizési, illetve evezési időt jelentik. Írja a standard output első és egyetlen sorába a minimális óraszámot, amennyi idő alatt teljesíthető mindenkinek a tréning.
Magyarázat: a helyes sorrend: 3, 1, 2.
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 s93.zip állományban a program forráskódja (s93.pas, s93.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 (s93.txt, s93.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.
(10 pont)
Figyelem!
Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.