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 2015. á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ő 2015. május 11-én LEJÁRT.


I. 373. A szöveg formázásának hatékony módja a stílusok alkalmazása. Használatuk esetén az egyes szövegegységek jellemzőit nem egyenként, hanem a hozzájuk rendelt stílusok segítségével állítjuk be. A legtöbb programban a stílusok nem önállóan létező elemek, hanem fastruktúrába rendezhetők. Egy szövegegység adott tulajdonságát a helyben, egyedileg megadott érték határozza meg. Ha az hiányzik, akkor a hozzárendelt stílusban vagy a struktúrában a felette levő stílusok közül a hozzá legközelebbiben szereplő beállítás a meghatározó.

A feladatban a fentiek leegyszerűsített modelljével dolgozunk: a szövegegységek bekezdések, a tulajdonságaik pozitív egészek. Készítsünk programot i373 néven, amely a stílusok leírását a lehető legtömörebbé alakítja, az egyes szövegrészek tényleges jellemzőit pedig meghatározza.

A bemeneti fájl két részből áll. Az első rész első sora a tárolt stílusok \(\displaystyle s\) száma. A következő \(\displaystyle s\) sor egy-egy stílus leírását tartalmazza. Az első karakter a stílus neve (az angol ábécé nagybetűje), a következő a struktúrában felette lévő stílus neve (a fa csúcsa esetén önmaga), majd a tulajdonság-érték párosok (az angol ábécé kisbetűje-pozitív szám). Az értékeket pontosan egy szóköz választja el. A következő sorban a szöveg bekezdéseinek \(\displaystyle b\) száma található, amely legfeljebb 500 lehet. A következő \(\displaystyle b\) sorban egy-egy bekezdés leírása található. Az első karakter az alkalmazott stílus neve, majd a bekezdésben egyedileg érvényes tulajdonság-érték párosok olvashatók az előző részhez hasonló formában.

A kimeneti fájl szerkezete pontosan egyezik a bemeneti fájl szerkezetével. Az első rész tartalmazza az egyszerűsített stílusokat, ahol azok a tulajdonságok nem jelennek meg, amelyek nem módosítják a struktúrában felettük lévő stílusokban beállított értékeket. A második részben az egyes bekezdésekben ténylegesen érvényre jutó tulajdonságok jelenjenek meg.

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 i373.zip állományban a program forráskódja (i373.pas, i373.cpp, ...), valamint a program rövid dokumentációja (i373.txt, i373.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. 374. Egy Magyarországra most érkező autógyártó kereskedelmi pontokat és márkaszervizeket hoz létre vidéki városainkban, többnyire a megyeszékhelyeken és megyénként néhány nagyobb településen. A motelep.csv tabulátorokkal tagolt, UTF-8 kódolású szöveges állományban rendelkezésre áll az ország városainak neve, a városok térképes elhelyezéséhez \(\displaystyle X\) és \(\displaystyle Y\) koordináták (méter mértékegységben), valamint a megye, amelyhez a város tartozik és - amelyik városban lesz - a létesítendő telephely neve. Oldjuk meg táblázatkezelő program segítségével a következő feladatokat. A megoldást mentsük i374 néven a táblázatkezelő alapértelmezett formátumában. A megoldáshoz rendelkezésre áll még egy momegyek.png nevű kép, amely Magyarország megyetérképét tartalmazza. Mindkét állomány honlapunkról letölthető.

1. Töltsük be a motelep.csv állományt egy munkalap A1-es cellájától kezdve és nevezzük át a munkalapot városok névre. A táblázat fejléce álljon a Város, TérképX, TérképY, Megye és Telephely szavakból, melyek jelenjenek meg félkövér betűstílussal, szürke háttérszínnel, vízszintesen középre igazítva.

2. Az \(\displaystyle X\) és \(\displaystyle Y\) koordinátákat kerekítsük egészre, majd az eredeti adatokat cseréljük le a kerekített értékekre, és a továbbiakban ezekkel számoljunk. A munkalap nem üres celláit szegélyezzük vékony szegéllyel. Az adatokat rendezzük a megye, illetve azon belül a városok neve szerint.

3. Készítsünk diagramot, amelyen ábrázoljuk a városokat egy városok diagram munkalapra. A városok helyét jelentő körvonal nélküli körök RGB \(\displaystyle (132,60,12)\) színnel legyenek kitöltve.

4. A diagram rajzterületének háttereként a momegyek.png képet adjuk meg. A diagram tengelyeit úgy állítsuk be, hogy ne kerüljön város az országhatáron túlra, és a Budapest körüli települések is nagyjából a főváros határához kerüljenek. Legnyugatibb városunk, Szentgotthárd, valamint a fővárostól észak felé eső Balassagyarmat éppen a határvonalon legyenek.

5. A diagramnak ne legyen jelmagyarázata. A ,, Magyarország városai és megyéi'' diagramcím a bal felső részben, Magyarországon kívül, a jelölőkkel azonos betűszínnel és narancssárga RGB \(\displaystyle (255,230,153)\) háttérszínnel jelenjen meg. A tengelyeket és vezetőrácsokat ne jelenítsük meg a diagramon.

6. Szűrjük ki egy másik munkalapra a városok közül azoknak az összes adatát, amelyeken telephelyet létesít majd a gyár. Ezt a munkalapot telephely névre nevezzük is át, és formázzuk a városok munkalap megjelenéséhez hasonlóan. Hozzunk létre a telephely diagram nevű munkalapon egy az előzővel megegyező formátumú diagramot a telephelyek városaiból, melynek diagramcíme ,,Magyarországi telephelyek'' szöveg legyen.

7. Készítsünk egy távolságok munkalapot, amely megadja az \(\displaystyle (X,Y)\) koordináták és a Pitagorasz-tétel segítségével az összes város és a telephelyként szereplő városok térkép szerinti távolságát. A munkalap A2 cellájától lefelé hivatkozással adjuk meg az összes város nevét, illetve a B1-es cellától jobbra rendre a telephelyek városainak nevét.

8. Az első oszlopban és az első sorban lévő városok közötti távolságot adjuk meg a sorok és oszlopok metszéspontjában található cellákban egy másolható képlet segítségével km mértékegységben, egész számként megjelenítve. A CA oszloptól vagy a 350. sortól segédcellák használhatók a számításokhoz.

9. Készítsünk egy keresés nevű munkalapot, amely alkalmas arra, hogy megmutassa, hol vannak egy adott városhoz az adott távolságon belüli telephelyek. Az A1-es cellába a  ,,Város'' szöveget írjuk, az A2-es cellába egy magyar város nevét, a B1-es cellába a ,,Telephely'' és a  C1 cellába a ,,Távolság'' szöveget. A B2-es cellában határozzuk meg a legközelebbi telephely városát és a C2-es cellában a két város távolságát km-ben. Ebben a cellában a meghatározott érték mellett jelenjen meg a ,,km'' mértékegység.

Beküldendő egy tömörített i374.zip fájlban a megoldás rövid leírása (i374.pdf), amely tartalmazza a használt táblázatkezelő program nevét és verzióját, valamint a megoldást adó táblázatkezelő munkafüzet (i374.xlsx, i374.ods, ...).

Letölthető fájlok: momegyek.png, motelep.csv.

(10 pont)

megoldás, statisztika


I. 375. Készítsük el a közlekedési csomópont probléma mechanikai modelljének számítógépes változatát.

A probléma lényege: adott három város, egy közös közlekedési csomóponthoz szeretnének utat építeni úgy, hogy az összköltség minimális legyen. Az eredeti probléma mechanikai interpretációját Pólya György adta, amelynek lényege: helyezzünk el a három pontban egy-egy csigát, azokon vessünk át egy-egy kötelet, amelyet fogjunk össze egy közös pontban, a túlsó végükre pedig egy-egy azonos nagyságú súlyt erősítsünk. A rendszer egyensúlyi állapota - amikor a közös pontban ható erők kioltják egymást - adja meg a csomópont helyét. (Pólya György: Indukció és analógia, Gondolat, 1988, 165-171.)

A fenti rendszert általánosítsuk \(\displaystyle n\) pontra. A megjelenítést egyszerűsítsük azzal, hogy a csigákat a pontokat tartalmazó síkon egy adott helyen vágott lyukkal helyettesítjük. A fonalakat egy közös pontból a lyukakhoz vezetett szakaszokkal ábrázoljuk. (A közös pont a lyukon nem haladhat át.) A modell 3 pontra itt tekinthető meg: http://demonstrations.wolfram.com/PolyasMechanicalModelForTheFermatPoint/.

A számítógépes modell a következőképpen legyen használható:

\(\displaystyle \bullet\) \(\displaystyle n\) értékét a 3 és 8 között szabadon megadjuk;

\(\displaystyle \bullet\) a lyukak helyét a felületen megadhatjuk, de véletlenszerű elhelyezést is választhatunk;

\(\displaystyle \bullet\) a program az egyensúlyi helyzet felé lépésenként halad az alábbiak szerint:

\(\displaystyle a.\) a felületet felülnézetből látjuk;

\(\displaystyle b.\) a közös pontra ható erőket a belőle induló, fonálirányban mutató egységvektorokkal szemléltetjük;

\(\displaystyle c.\) léptetéskor az összeköttetési pontot a program a fenti egységvektorok eredőjének irányába mozdítja.

A megoldást bármely programozási eszközzel elkészíthetjük. Ügyeljünk a szép megjelenésre és a könnyű használhatóságra.

Beküldendő egy tömörített (i375.zip) állományban a megoldás leírása (i375.pdf), amely tartalmazza megoldás lényeges lépéseinek ismertetését; valamint a program forrásnyelvi változata és a fordításához és működéséhez szükséges fájlok.

(10 pont)

megoldás, statisztika


S-jelű feladatok

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


S. 98. Szeretnénk a számítógépünket felújítani, ezért vásárolnunk kell bele néhány alkatrészt, így a régieket az újakra tudjuk cserélni. A lehető legolcsóbban szeretnénk a felújítást elvégezni, így a legkevesebb alkatrészt szeretnénk megvásárolni (mindegyik azonos árban van). Viszont előfordulhat, hogy valamilyen összetartozó \(\displaystyle k\) db alkatrész közül \(\displaystyle k-1\)-et újra cserélünk, ekkor kötelezően a \(\displaystyle k\)-adikat is ki kell cserélni. A boltban összesen \(\displaystyle N\) (\(\displaystyle 1\le N\le 1\;000\;000\)) típusú alkatrész található (1-től \(\displaystyle N\)-ig számozva). Az összetartozó csoportok mérete bármekkora lehet, de összes méretük legfeljebb 250000 lehet. Tudjuk továbbá azt is, hogy az 1-es számú alkatrészt mindenképp ki kell cserélnünk.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle C\)-t (a csoportok számát), majd a következő \(\displaystyle C\) sorból a csoportban lévő alkatrészek \(\displaystyle \mathrm{db}_i\) számát, majd a csoportban lévő alkatrészek típusát \(\displaystyle \mathrm{db}_i\) darab 1 és \(\displaystyle N\) közötti egész formájában. A két csoportnak akár közös elemei is lehetnek. A program írja a standard output első sorába a megvásárolandó alkatrészek minimális számát. Magyarázat: a példában az 1, 2, 3, 4-es számú alkatrészeket kell megvenni.

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 s98.zip állományban a program forráskódja (s98.pas, s98.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 (s98.txt, s98.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.