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 2013. márciusi 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ő 2013. április 10-én LEJÁRT.


I. 316. Egy logikai kifejezés elemi állításait az angol ábécé nagybetűivel jelöljük. A logikai kifejezés leírása során a nem, az és, vagy és az implikáció műveleteket használjuk, amelyeket rendre a !, &, |, > karakterekkel jelöljük. A műveletek végrehajtási sorrendjét zárójelezéssel módosíthatjuk.

Írjunk programot, amely a kifejezés kiértékelésének lépéseit mutatja be a következő módon. Keressük meg az egyik legelőször kiértékelhető részét a kifejezésnek, majd nevezzük el az angol ábécé egy kisbetűjével. Az eredeti kifejezésbe helyettesítsük be ezt a betűt, majd kezdjük elölről. A folyamat végén a kifejezés az angol ábécének csupán egyetlen kisbetűjét fogja tartalmazni.

A bemeneti fájl egyetlen sora tartalmazza a feldolgozandó logikai kifejezést, amely legfeljebb 80 karakter hosszú. A kimeneti fájl sorai a kiértékelés lépéseit mutatják be. Minden sor két részből áll. Az első rész az angol ábécé egy, még nem használt kisbetűjével kezdődik, majd az egyenlőségjelet követően a kifejezés első kiértékelésre kerülő részével folytatódik. Egy szóközt követően a kifejezést írjuk át úgy, hogy abba - a kiértékelésre kerülő rész helyére - a sorbeli kisbetűt írjuk.

A program első parancssori argumentuma a bemeneti fájl, a második argumentuma pedig a kimeneti fájl neve legyen.

Beküldendő a program forráskódja (i316.pas, i316.cpp, ...), valamint a program rövid dokumentációja (i316.txt, i316.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)

megoldás, statisztika


I. 317. A Központi Statisztikai Hivatal minden évben közzé teszi a magyarországi települések alapvető adatait. Az I. 305. feladatban a 2011. január 1-jén kiadott adatok segítségével kellett az alábbiak szerint adatbázist létrehozni. A mostani feladatban szereplő lekérdezéseket ugyanazon adathalmaz alapján készítjük el. Az adathalmaz érdekessége, hogy a fővárost nem tartalmazza egységében, hanem kerületenkénti bontásban vannak benne az adatai.

1. Hozzunk létre i317 néven egy üres adatbázist! Importáljuk az adatbázisba a helyseg, kisterseg, megye, megyeresz, onkormanyzat, telepulestipus, kisebbseg táblákba az ezekkel az elnevezésekkel azonos nevű txt fájlokból az adatokat! (A fájlok UTF-8 kódolású, tabulátorral tagoltak, első sorukban a mezőazonosítók találhatók.) A táblák kapcsolatát leírásuk utáni ábra mutatja!

Táblák:

2. Készítsünk lekérdezést, amely megadja azokat a megyei jogú városokat, amelyek nem megyeszékhelyek a megyéjük nevével együtt! (2megyeijoguvarosok)

3. Készítsünk lekérdezést arról, hogy a főváros melyik kerületében található a legkevesebb kisebbségi önkormányzat, és szám szerint mennyi!\ (3keveskisebbseg)

4. Adjuk meg azoknak a településeknek a nevét, kistérségét és megyéjét, amelyek nevében szerepel a ,,magyar'' szó szórészletként! (4magyarok)

5. Lekérdezéssel adjuk meg azoknak a kistérségeknek a nevét, megyéjüket, a hozzájuk tartozó települések számát, és azok összlakosságát, amely kistérségekhez húsznál több település tartozik! A lista a megyék neve szerint legyen rendezett! (5nagykistersegek)

6. Soroljuk fel lekérdezéssel, hogy melyik kisebbségnek nincs kisebbségi önkormányzata egyetlen Heves megyei településen sem! (6hevesbennincs)

7. A magyar lakosság hány százaléka él városokban? Vegyük figyelembe, hogy a városnak minősített településeken kívül számításba kell venni a megyei jogú város; megyeszékhely,megyei jogú város továbbá a fővárosi kerület besorolású települések lakosságát is! (7varoslakok)

8. Lekérdezéssel adjuk meg, hogy melyik megyében hány város, illetve a fővárosban hány kerület található! Ennél a lekérdezésnél is számítsuk a városok közé a városnak minősített településeken kívül a megyei jogú város; és a megyeszékhely, megyei jogú város besorolású településeket is! (8varosszam)

9. Megyénként, és azon belül településtípusonként mennyi az egy lakásban élők átlagos száma? (9lakok)

10. Melyek azok a megyék, amelyekben a lakosságnak több mint a fele falun, vagyis, községben vagy nagyközségben él? (10falusitobbseg)

Beküldendő az adatbázis (i317.mdb, i317.accdb, i317.odb, ...), illetve egy rövid dokumentáció (i317.txt, i317.pdf, ...), amelyben szerepel a megoldáskor alkalmazott adatbázis-kezelő neve, verziószáma.

(10 pont)

megoldás, statisztika


I. 318. A kottaírást a hangok, a ritmusok, a dallamok és az ezekhez tartozó információk lejegyzéséhez használjuk. Kottakiadással a zenemű- és könyvkiadók foglalkoznak. A jogdíjak és a kiadványok kis példányszáma miatt az áruk általában borsos. Ugyanakkor az interneten is lehet találni igényes kiadványokat. Például:

Készítsük el valamelyik ismert könnyűzenei mű kottáját. A megoldáshoz ajánljuk a MuseScore nevű (internetről ingyenesen letölthető) programot. (A programról, a használatáról leírás olvasható a http://musescore.org/hu oldalon, illetve oktatófilmek találhatók az ismert videómegosztókon.) A szerkesztőprogram az elkészített kottát képes hangszintetizátor segítségével megszólaltatni.

Forrásként papíralapú és interneten található kiadványokat, kottákat is használhatunk. A zenei mű stílusa a könnyűzenén belül tetszőleges. A kotta hossza minimum 3 sor és maximum 2 oldal legyen.

Beküldendő egy tömörített állományban (i318.zip) a kotta a szerkesztőprogram alapértelmezett formátumában (mscz), valamint egy rövid dokumentáció (i318.txt, i318.pdf, ...), amely tartalmazza a forrásként használt mű pontos hivatkozását.

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2013. április 10-én LEJÁRT.


S. 79. Adott egy súlyozott N csúcsú, M élű gráf: N\le 100\;000, M\le 100\;000. Adjuk meg minden e élre, hogy létezik-e e-t tartalmazó minimális feszítőfa. Minimális feszítőfának egy minimális összsúlyú feszítőfát nevezünk. Feszítőfa egy olyan fa, mely a gráf összes csúcsát, illetve az éleinek egy részhalmazát tartalmazza. Fának pedig egy olyan gráfot nevezünk, mely körmentes. Egy minimális feszítőfa tartalmazza e-t, ha egy olyan minimális feszítőfa, melynek az e az egyik éle. A program olvassa be a standard input első sorából N-et és M-et, majd a következő M sorból a ki, vi, si szóközzel elválasztott egészeket: azaz a ki kezdőpontú, vi végpontú, si súlyú éleket, és írja a standard output i-edik sorába az ,,Igen'' szót, ha létezik olyan minimális feszítőfa, mely az i-edik élet tartalmazza, és a ,,Nem'' szót, ha nem létezik ilyen.

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. Kapható részpontszám a 9 pontból, ha a program csak kisebb tesztesetekre tud lefutni időben. Az alábbi korlátok érvényesek az egyes részmegoldásokra:

\bullet 2 pontért: 0<M\le300;

\bullet további 3 pontért: 300< M\le 2\;000;

\bullet további 4 pontért: 2\;000< M\le 100\;000.

Beküldendő egy tömörített s79.zip állományban a program forráskódja (s79.pas, s79.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 (s79.txt, s79.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(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.