A KöMaL 2015. októberi 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ő 2015. november 10-én LEJÁRT. |
I. 382. A ZUMA egy többféle elrendezésű pályán játszott lövöldözős játék. A játék során a pályán mozgó, kezdetben folytonos sort alkotó, különböző színű golyókat kell lövések segítségével eltüntetni, mielőtt azok bármelyike elérné a pálya végét. Készítsünk programot, amelyben a játékot egy egyenes szakaszon játsszuk, a golyók balról jobbra mozognak és minden időegységben egy lövés történik.
Szabályok:
\(\displaystyle \bullet\) a golyók kezdetben a pálya bal oldalán helyezkednek el, közöttük golyó nélküli pozíció nincs;
\(\displaystyle \bullet\) balról az első golyó minden időegységben egy egységgel tolódik jobbra;
\(\displaystyle \bullet\) minden olyan golyó tolódik, amelynek a szomszédja tolódik;
\(\displaystyle \bullet\) a kilőtt golyó tolódás után ér célba, de még ugyanabban az időegységben
\(\displaystyle \circ\) ha a találat helyén golyó van, akkor
\(\displaystyle *\) ha a találat helyén és közvetlenül mellette azonos színű golyók voltak egymás mellett;
- azokat eltünteti, helyük üres lesz;
- amíg az üressé váló rész két oldalán együttvéve 3 vagy több azonos színű golyó van, azok is eltűnnek;
\(\displaystyle *\) különben a kilőtt golyó a találat helyére kerül, az ott lévő golyó pedig jobbra tolódik és a jobbra lévő golyók közül mindazok tolódnak, amelyek szomszédja tolódik;
\(\displaystyle \circ\) ha a találat helyén nincs golyó, akkor
\(\displaystyle *\) ha valamely szomszédjában van golyó, a golyó a célhelyen marad;
\(\displaystyle *\) különben a golyó eltűnik.
A bemeneti fájl első sora a pálya \(\displaystyle h\) hosszát, a pályán lévő golyók \(\displaystyle p\) számát és a játék során kilőtt golyók \(\displaystyle k\) számát tartalmazza. A második sor \(\displaystyle p\) darab karaktert tartalmaz, amely a golyók színét jelöli, amelyek sorrendben a pálya bal szélétől helyezkednek el. (A golyók színét az A, ..., F karakterek jelölik.) A következő \(\displaystyle k\) sor egy-egy golyó-hely párt tartalmaz: a páros első tagja a golyó színét jelöli, a második tagja pedig a pozíciót, amelyen a golyó a pályát eléri. A kimenet a rendszer állapotát mutatja az utolsó lövést követően.
\(\displaystyle \bullet\) Ha az összes golyót sikerült lövésekkel eltüntetni, akkor az első sorba 0 kerüljön, a második sorba azon lövés sorszáma, amely után ez először teljesült.
\(\displaystyle \bullet\) Ha valamely golyó elérte a pálya végét, akkor az első sorba a -1 kerüljön, a második sorba pedig azon lövés sorszáma, amely után ez történt.
\(\displaystyle \bullet\) Ha van még golyó a pályán, de egy sem érte el a végét, akkor az első sor az 1 értéket tartalmazza, a második sor pedig \(\displaystyle h\) darab karaktert, amely a pályán lévő golyók színét jelöli balról jobbra. Az üres pozíciókra . kerüljön.
Az alábbi példa sorai egy-egy, egymástól független állapotokban bekövetkezett lövést és annak eredményét mutatják.
A program első parancssori argumentuma a bemeneti fájl neve, a második pedig a kimeneti fájl neve legyen.
Beküldendő egy tömörített i382.zip állományban a program forráskódja, valamint a program rövid dokumentációja, 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. 383. A magyarországi hatósági engedéllyel rendelkező bányászati területek néhány adata áll rendelkezésünkre a telek.txt, a banya.txt és a nyersanyag.txt állományokban. Az állományok tabulátorral tagolt, UTF-8 kódolású szövegfájlok, az első sorok a mezőneveket tartalmazzák.
Készítsünk új adatbázist i383 néven. A mellékelt adatállományokat importáljuk az adatbázisba a forrásállományokkal azonos néven. Beolvasáskor állítsuk be a megfelelő adatformátumokat és kulcsokat, a táblákba ne vegyünk fel új mezőt.
Táblák:
Készítsük el a következő feladatok megoldásait. Az egyes lekérdezéseknél ügyeljünk arra, hogy mindig csak a kért értékek jelenjenek meg és más adatok ne. A megoldásokat a zárójelben lévő néven mentsük el.
1. Soroljuk fel lekérdezés segítségével azoknak a településeknek a nevét, ahol zártak be mélyművelésű bányát. A listában minden településnevet egyszer jelenítsünk meg. (3bezart)
2. Melyik a legvastagabb szénrétegű bányatelek? Adjuk meg a település nevét és a szénréteg vastagságát. (4sokszen)
3. Lekérdezéssel határozzuk meg, hogy a kavicsot termelő bányák milyen más nyersanyagot termelnek, illetve termelhettek még ki. A listában a kavics ne jelenjen meg. (5kavics)
4. Adjuk meg a működő bányák közül azokat, ahol 400 és 500 méter tengerszint feletti magasságból nyersanyag termelhető ki. A listában a bánya települése és a bányászott nyersanyag jelenjen meg. (6magas)
5. A szénhidrogének - halmazállapottól függetlenül - általában együtt fordulnak elő. Lekérdezés segítségével listázzuk ki azokat a településeket, ahol a bányatelkeken kőolaj és földgáz kitermelése együtt történik. A listában a települések neve és a feltételnek eleget tevő bányatelkek száma jelenjen meg. (7szenhidrogen)
6. A fedőszint és a feküszint alapvető információ a bányatelkekről. Az adatbázis karbantartásához ezeket az adatokat be kell szerezni. Készítsünk jelentést azokról a bányatelkekről, ahol a két adat közül legalább az egyik hiányzik. A jelentésben a települések nevét emeljük ki, bányatelkenként adjuk meg a telek azonosítóját, a bányászott ásványi nyersanyag nevét és az esetleg ismert fedőszint, valamint feküszint értékét. A jelentés létrehozását lekérdezéssel vagy ideiglenes táblával készítsük elő. A jelentés elkészítésekor a mintából a mezők sorrendjét, a címet és a mezőnevek megjelenítését vegyük figyelembe. A jelentés formázásában eltérhetünk a mintától. (8hiany)
7. A külfejtés, illetve a külfejtés és mélyművelés nyersanyag kitermelési módszer a tájat durván átrendezi. Lekérdezés segítségével határozzuk meg, hogy hány települést érint ilyen művelési módú bányatelek. (9tajrombolas)
Beküldendő egy tömörített i383.zip állományban az adatbázis és egy rövid dokumentáció, amelyből kiderül az alkalmazott adatbázis-kezelő neve, verziószáma.
Letölthető fájlok: nyersanyag.txt, banya.txt, telek.txt (banyak.zip).
(10 pont)
I. 384. Készítsünk alkalmazást egyszerű (hurok- és többszörös élek nélküli) gráfok szerkesztésére. A program legyen alkalmas legföljebb 20 csúcsot tartalmazó gráf vizuális szerkesztésére, valamint szöveges állományba mentésére és beolvasására.
Szerkesztéskor az üres rajzterületen történő kattintás jelentse egy új csúcspont fölvételét. Két csúcsra kattintás egymás után jelentse az elsőt a másodikkal összekötő (irányítatlan) él berajzolását, ha még nem voltak összekötve; illetve az él törlését, ha már össze voltak kötve. A jobb egérgombbal történő hasonló művelet jelentse irányított élek rajzolását és törlését. Csúcsot a fölötte lenyomva tartott egérgombbal lehessen mozgatni. A csúcsok kapjanak 1-től kiindulva sorszámot. Csúcsot törölni a csúcsra történő dupla kattintással lehessen. Ha egy csúcsot törlünk, akkor természetesen minden élét is töröljük, ugyanakkor minden nála nagyobb sorszámú csúcs száma csökkenjen eggyel. Így egy \(\displaystyle N\) csúcsú gráfban a sorszámok mindig 1-től \(\displaystyle N\)-ig terjedjenek. A csúcsokat ábrázoljuk egyszerű körként, a sorszámukat írjuk a kör belsejébe. Az éleket szakaszként rajzoljuk, az irányított éleket a szakasz végén nyíllal jelöljük. A programnak nem kell megoldania olyan megjelenítési problémákat, hogy csúcsok körei átfedik egymást vagy egy nem a csúcsba befutó élt. Tételezzük föl, hogy a programot egy ügyes felhasználó kezeli, aki igyekszik a gráf jó elrendezésére.
A program az M gomb megnyomására vagy a menüből kiválasztva a Mentés funkciót írja egy graf.txt szöveges állományba a gráf adatait. Az állomány első sorában a csúcsok száma (\(\displaystyle N\)) és az élek száma (\(\displaystyle E\)), valamint a rajzterület szélessége és magassága legyen egy-egy szóközzel elválasztva, a következő \(\displaystyle N\) sorban a csúcsok grafikus szerkesztéskor alkalmazott koordinátái (egész számpárok szóközzel elválasztva), majd a következő \(\displaystyle E\) sorban a gráf élei (egész számpárok szóközzel elválasztva) szerepeljenek. A program a B gomb vagy a Beolvasás funkció esetén törölje a munkaterület és olvassa be a graf.txt állományt további szerkesztésre.
A megoldáshoz a versenykiírásban szereplő programozási nyelveket és fejlesztőeszközöket használhatjuk, illetve kliens oldalon futó webes alkalmazásokat is elfogadunk.
Beküldendő egy i384.zip tömörített állományban a program forráskódja, valamint a program rövid dokumentációja, 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/S-jelű feladatokA beküldési határidő 2015. november 10-én LEJÁRT. |
I/S. 2. Adjuk meg a lexikografikusan rendezett \(\displaystyle n\) hosszú permutációk közül a \(\displaystyle k\)-adikat (\(\displaystyle 1\le n\le 14\) és \(\displaystyle 1\le k\le n!\)). Egy \(\displaystyle n\) hosszú permutációnak az \(\displaystyle 1,2, \ldots, n\) számok egy sorbarendezését nevezzük. Két permutációt úgy tudunk lexikografikusan rendezni, hogy balról az első helyen, ahol eltérnek a számok számjegyei egymástól, a kisebb számot tartalmazó permutációt soroljuk előrébb. Például \(\displaystyle 2314< 2341\).
A program olvassa be a standard input első sorából \(\displaystyle n\)-et és \(\displaystyle k\)-t, majd írja a standard output első és egyetlen sorába a megfelelő permutációt.
|
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 is2.zip állományban a program forráskódja az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.
(10 pont)
 |
S-jelű feladatokA beküldési határidő 2015. november 10-én LEJÁRT. |
S. 101. Adott egy hegység térképe, pontosabban egy \(\displaystyle N\times M\)-es táblázat az egyes koordináták magasságával, melyek egyike sem nagyobb, mint \(\displaystyle 1\,000\,000\,000\). Továbbá adott néhány nagyon szép hely a hegységben. Azt szeretnénk eldönteni, hogy legalább mennyire nehéz az a túra, amely minden szép helyet meglátogat valamelyik szép helyről kiindulva. Azaz formálisan a legkisebb \(\displaystyle C\) számot szeretnénk meghatározni, hogy bármelyik szép helyről bármelyik másikra el lehessen jutni úgy, hogy közben a térképen egy mezőről mindig egy másik olyan élszomszédos mezőre lépünk, melyek szintkülönbsége legföljebb \(\displaystyle C\).
A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle M\)-et, a térkép sorainak és oszlopainak számát (\(\displaystyle 1\le N, M\le 800\)), majd a következő \(\displaystyle N\) sorból soronként \(\displaystyle M\) db egészet: a magasságokat. Az utána következő \(\displaystyle N\) sorból is soronként \(\displaystyle M\) db egészet, melyek 0-k, vagy 1-ek lehetnek: 0, ha nem szép a hely, és 1, ha szép. A program írja a standard output első és egyetlen sorába a lehető legkisebb megfelelő \(\displaystyle C\) számot.
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 s101.zip állományban a program forráskódja az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja, 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.