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 2016. szeptemberi 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ő 2016. október 10-én LEJÁRT.


I. 406. Különböző élhosszúságú kockákból tornyokat építünk, és azokat kívülről lefestjük egy automatával. A tornyoknak stabil felépítésűeknek kell lenniük, majd festésükkor az automata mind a négy oldalról és felülről lefesti azokat.

Rendelkezésre áll \(\displaystyle K\) darab kocka véletlenszerű sorrendben. A kockák élhosszai egész számok. Az automata programja szerint igyekszik minél magasabb tornyot építeni, majd befesteni a következő szabályok szerint:

– A kockákat sorrendben egymás után használja föl.

– Kockát olyan torony tetejére tehet, ahol az eddigi legfelső kocka nem kisebb az elhelyezendőnél.

– A soron következő kockát arra a toronyra teszi, ahol a legfelső a lehető legkisebb olyan, amire még rátehető. Ha több ilyen torony van, akkor a kisebb sorszámút (amelyiket előbb kezdte el építeni) választja. Amennyiben a kocka egyikre sem tehető, akkor új tornyot kezd.

– Miután a kockák elfogytak, a kész tornyokat festékszóró festi be minden oldalról és felülről, de alulról és a kockák között nem.

Rendelkezésünkre áll és a honlapunkról letölthető egy minta az automata bemenetére a kockak.txt állományban.

Az állomány első sorában \(\displaystyle K\) (\(\displaystyle 0\le K\le 1\,000\)) a kockák száma olvasható, az ezt követő \(\displaystyle K\) sor mindegyike az egyes kockák \(\displaystyle M_i\) élhosszát (\(\displaystyle 1\le M_i \le 50\)) tartalmazza.

Készítsünk programot i406 néven, amely megoldja az alábbi feladatokat.

A képernyőre írást igénylő részfeladatok eredményének megjelenítése előtt írjuk a képernyőre a feladat sorszámát (például 4. feladat:). A beolvasás előtt a várt tartalomra vonatkozó üzenetet jelenítsünk meg. Az ékezet nélküli kiírás is megengedett.

1. Olvassuk be a kockak.txt állomány adatait és a következő feladatokat ezek alapján oldjuk meg.

2. Írjuk ki a képernyőre az automata által felépített tornyok számát.

3. Írjuk a képernyőre egy sorba, szóközzel elválasztva a legmagasabb tornyot alkotó kockák élhosszúságát és ezek összegét, vagyis a torony magasságát. Ha több ilyen van, akkor a legkisebb sorszámú toronyét jelenítsük meg.

4. Írjuk a képernyőre annak a toronynak a sorszámát, amelyben a legtöbb azonos élhosszúságú kocka van (több ilyen torony esetén a legkisebb sorszámút).

5. Szabályosnak nevezünk egy legalább 3 kockából álló tornyot akkor, ha a kockák oldalélei alulról felfelé haladva számtani sorozatot alkotnak. Írjuk a képernyőre a szabályos tornyok számát.

6. Kérjük be a felhasználótól egy torony sorszámát, majd írjuk ki szóközzel elválasztva egy sorba, hogy

\(\displaystyle a.\) mekkora területet festett be az automata a tornyon;

\(\displaystyle b.\) a tornyot szétszedve a kockákon összesen hány területegységet nem festett be az alsó oldalakat is figyelembe véve.

7. Írjuk a képernyőre, hogy az első torony felső szintjeiből hány kockát lehetne a legutolsó toronyra átrakni egyben, a méretre vonatkozó szabályok betartásával.

Beküldendő egy tömörített i406.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

Letölthető fájl: kockak.txt.

(10 pont)

megoldás, statisztika


I. 407. A keresztény húsvét napja a naptárban évről évre változik, helyét az első niceai zsinat (Kr. u. 325) határozta meg. Eszerint húsvét napja a tavaszi napéjegyenlőség utáni első holdtöltét követő vasárnap.

Húsvét napjának kiszámítását a középkori matematika egyik fontos alkalmazásának tartották. Az első, csak számolást igénylő, gyors eljárást Gauss alkotta meg. Gauss módszerének részletes leírását megtalálhatjuk például a Wikipedia Húsvétképlet vagy Húsvétszámítás szócikkében.

1. Készítsünk táblázatkezelő program segítségével, képletek alkalmazásával táblázatot, amely 1583-tól 2299-ig Gauss módszerének alkalmazásával meghatározza, hogy húsvét vasárnapja az adott évben melyik hónap melyik napjára esik.

2. A Gauss által adott eljárás utolsó lépésében – bizonyos feltételek fennállása esetén – módosítani kell az időpontot, ha az április 25-re vagy 26-ra esne. Emeljük ki feltételes formázás segítségével, halványpiros háttérrel azoknak az éveknek a sorait, ahol ezt a módosítást meg kellett tennünk.

Beküldendő egy tömörített i407.zip állományban a megoldást tartalmazó munkafüzet és a megoldás rövid leírását bemutató dokumentáció.

(10 pont)

megoldás, statisztika


I. 408. Az egyre jobban terjedő elektronikus könyvek – a weblapokhoz hasonlóan – lényegében HTML kódú fájlok, ahol a dokumentum megjelenítését főleg stílusok segítségével (CSS állomány használatával) adhatjuk meg. Elektronikus könyvek előállításához ingyenesen elérhető programok állnak rendelkezésünkre, ilyen például az elektronikus könyvek katalogizálására kifejlesztett Calibre is. Az egyik széles körben elterjedt, ingyenesen hozzáférhető, nyílt forráskódú szabvány pedig az ePub.

Készítsük el a mese.txt fájlban forrásként megadott, a Magyar Elektronikus Könyvtárból származó meseválogatást ePub formátumú elektronikus könyvként az alábbi leírásnak megfelelően. (A nem megadott beállításokat hagyjuk meg a szerkesztőprogram alapértelmezett formátumában.)

1. Az alapértelmezett betűtípus a forrásként megadott, ingyenesen elérhető Gemerald font legyen.

2. A főszöveg bekezdéseinek első sora kezdődjék 5%-kal beljebb, a bekezdések sorköze 1,25 legyen, a bekezdések között ne legyen térköz.

3. A mesék címét kettes szintű címsor stílussal formázzuk meg. Minden mese új oldalon kezdődjék.

4. A h2 stílusú bekezdések betűmérete legyen a főszöveg betűméretének 1,5-szerese, előtte legyen 1, utána 0,5 sornyi távolság, a sorköz legyen szimpla, az első sorok behúzása 0.

5. A farkastanya című mese végén lévő vers középre zártan, szimpla sortávolsággal, dőlt betűstílussal jelenjen meg.

6. Az első oldalon a szerző neve, a mű címe és a ,,(részletek)'' szöveg egyaránt egyes szintű címsor legyen. A h1 stílusú bekezdések középre zártan, a főszöveg betűméretének kétszeresével, félkövér betűstílussal jelenjenek meg. A címsorok alatt a forrás megjelölése előtt legalább 5 sornyi térköz legyen.

7. Készítsünk a könyvhöz tartalomjegyzéket, amelyben csak a mesék címei jelennek meg.

8. Állítsuk be a metaadatokat a következő módon: a szerző Arany László, a cím Magyar népmesék (részletek), a címke pedig mesék.

9. A könyvhöz készítsünk tetszőleges, de a szerző nevét és a mű címét tartalmazó borítót.

Beküldendő egy i408.zip tömörített állományban az ePub formátumú elektronikus könyv és a dokumentáció, amely tartalmazza a megvalósítás rövid leírását.

Letölthető állomány: mese.txt, Gemerald.ttf, Minta.pdf.

(10 pont)

megoldás, statisztika


I/S-jelű feladatok

A beküldési határidő 2016. október 10-én LEJÁRT.


I/S. 10. A Ritka család minden tagjának különböző keresztneve van. Rendelkezésünkre áll a Ritka család felépítése szülő–gyerek kapcsolatok formájában.

Készítsünk programot is10 néven, amely megadja azokat a családban, akiknek \(\displaystyle K\) számú leszármazottja van.

A program standard bemenetén a családfát adjuk meg. Az első sor a szülő-gyermek kapcsolatok \(\displaystyle N\) (\(\displaystyle 1\le~N\le 20\,000\)) számát és \(\displaystyle K\) (\(\displaystyle 0\le K\le 20\)) értékét adja meg. Az ezt követő \(\displaystyle N\) sor egy-egy szülő és gyermek névpárt tartalmaz.

A program a standard kimenetre írja ki a család olyan családtagjainak számát, akiknek \(\displaystyle K\) leszármazottja van, majd a neveiket a következő sorban szóközzel elválasztva sorolja fel.

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. További 9 pontot ér, ha a program minden helyes bemenetet képes jól megoldani 1 mp futásidőkorláton belül. A programra kapható 9 pontból legföljebb 4 adható azokra a megoldásokra, amelyek csak az \(\displaystyle 1\le N\le 1000\) nagyságú bemenetekre adnak helyes megoldást az időkorláton belül.

Beküldendő egy tömörített is10.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

statisztika


S-jelű feladatok

A beküldési határidő 2016. október 10-én LEJÁRT.


S. 109. Egy vállalat \(\displaystyle N\) embert foglalkoztat. Mindenkinek legfeljebb két beosztottja (akiknek a sorrendje nem fontos), és pontosan egy felettese van, kivéve a főigazgatót, akinek nincs felettese. A munkatársakat az \(\displaystyle 1,\ldots, N\) számokkal azonosítjuk, az 1-es a főigazgató. A cég súlyos pénzügyi gondokkal küzd, ezért elhatározták, hogy átszervezik a beosztás rendszerét. Ehhez felvehetnek új munkatársakat, illetve megválhatnak bizonyos alkalmazottaktól. Ezenkívül az egyedüli megengedett művelet az azonosítószámok átírása. Minden egyes új munkatárs felvételéhez állásinterjút kell szervezni \(\displaystyle F\) krajcárért, valamint tudjuk, hogy az \(\displaystyle i\)-edik alkalmazott elbocsátása a végkielégítés miatt \(\displaystyle V[i]\) krajcárba kerül. Az azonosítók átírásának természetesen nincs költsége.

A cégvezetés megadta, hogy szerintük mi az optimális vállalati struktúra. A fenti feltételek erre a szerkezetre is igazak. Írjunk programot, ami megadja, hogy legalább hány krajcárt kell elkölteni az átalakításra.

A standard bemenet első sora az alkalmazottak \(\displaystyle N\) számát és egy új alkalmazott felvételének \(\displaystyle F\) költségét tartalmazza. A második sor \(\displaystyle N\) egész számot tartalmaz, az \(\displaystyle i\)-edik szám \(\displaystyle V[i]\), vagyis az \(\displaystyle i\)-edik alkalmazott végkielégítése. A harmadik sor \(\displaystyle N-1\) számot tartalmaz, az \(\displaystyle i\)-edik szám az \(\displaystyle (i+1)\)-edik beosztott felettesének a száma. A negyedik és ötödik sor az átalakítás után elérni kívánt struktúrát írja le: a negyedikben az alkalmazottak kívánt \(\displaystyle M\) száma található, míg az ötödikben \(\displaystyle M-1\) egész szám írja le a feletteseket a harmadik sorhoz hasonló módon.

A standard kimenet első és egyetlen sora tartalmazza az átalakítás minimális \(\displaystyle K\) költségét.

Korlátok: \(\displaystyle 1\le N\), \(\displaystyle M\le 5000\); \(\displaystyle 0\le V[i]\), \(\displaystyle F\le 10^5\); időlimit: 0,2 mp; memórialimit: 256 MB.

A verem (stack) méretére nincs külön korlát, ez is a teljes memóriába számít bele.

Magyarázat: elbocsátjuk a 5-ös számú alkalmazottat, és a 4-es számú alá felveszünk két új beosztottat. Ekkor a költség \(\displaystyle V[5]+2\cdot F = 2+2\cdot 1 = 4\). Ha átnevezzük a 2-est 3-assá, a 3-ast 2-essé, akkor megkapjuk a kívánt struktúrá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 a fenti korlátoknak megfelelően.

Beküldendő egy tömörített s109.zip állományban a program forráskódja, 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)

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.