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 2018. februári 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ő 2018. március 12-én LEJÁRT.


I. 448. Egy fanatikus kosárlabda-szurkoló előre szeretné megvenni a belépőjegyeket a bajnokság februártól májusig terjedő időszakának bizonyos mérkőzéseire. Kedvenc csapata a Voros_Rokak, de szívesen nézi a Computerbonto és a Bohocok meccseit is. Rendelkezésünkre áll, és honlapunkról letölthető a naptar.txt állomány, amely a mérkőzések adatait és a szurkolónak a belépők megvásárlására tervezett maximális pénzkeretét tartalmazza.

Az állomány első sorában a naptárban szereplő mérkőzések száma \(\displaystyle N\) (\(\displaystyle 1\le N\le 100\)) és a jegyvásárlásra szánt maximális pénzkeret \(\displaystyle P\) (\(\displaystyle 2000\le P\le 50\,000\)) található. Az ezt követő \(\displaystyle N\) sor az egyes mérkőzések négy adatát tartalmazza: a hazai csapat neve, az ellenfél csapatának neve, a nap sorszáma az éven belül és a jegyár. A mérkőzések egy napon belül sem kezdődnek egyszerre, a szervezők biztosítják, hogy elvileg mindegyik megtekinthető legyen.

Készítsünk programot i448 néven, amely megoldja az alábbi feladatokat, amelyekkel a szurkoló jegyválasztását segítjük. 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.

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

2. Írjuk ki a képernyőre, hogy a vizsgált időszakban a Voros_Rokak csapat hány mérkőzést játszik, és hogy mennyibe kerülne, ha a rajongó minden mérkőzésükre venne jegyet.

3. Határozzuk meg, hogy a Voros_Rokak melyik nap játssza először és utoljára otthon a mérkőzését.

4. Adjuk meg az adatok alapján, hogy mikor lesz utoljára olyan meccs, amikor a három kedvenc csapatból kettő egymás ellen mérkőzik.

Fanatikus szurkoló barátunk a megvásárlandó jegyek kiválasztásához a következő módszert alakította ki, amíg a pénze elegendő:

– Időrendben megveszi a Voros_Rokak minden mérkőzésének jegyét.

– Ár szerint növekvő sorrendbe állítja a Computerbonto és a Bohocok otthoni mérkőzéseit és ezeket veszi meg sorrendben, amíg a pénzéből futja.

– Azonos árú jegyek esetén először a Computerbonto, majd a Bohocok mérkőzésére, ezen belül időrendben vesz.

5. Adjuk meg szóközzel elválasztva, egy sorban, azon napok sorszámát növekvően rendezve, amelyekre jegyet fog venni.

6. Írjuk ki, hogy a három kedvenc csapatát (külön-külön) hány mérkőzésen fogja látni.

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

Letölthető fájl: naptar.txt

(10 pont)

megoldás, statisztika


I. 449. A helyi önkormányzati választásokon különböző szervezetek (nem feltétlenül csak pártok) indíthatnak jelölteket. A jelöltek egy része a választókerületekben méri össze népszerűségét, az lesz képviselő, aki a legtöbb szavazatot kapja.

Választási rendszerünkben azonban a többi jelöltre leadott szavazat sem vész kárba. Ezeket jelölőszervezetenként összeadják, az így kapott szám a jelölőszervezet ún. töredékszavazatainak száma. Minden jelölőszervezet készít egy ún. kompenzációs listát, ahonnan a kialakult töredékszavazatok számától függően a kiosztott mandátumok mellett még további képviselőket juttathat be az képviselőtestületbe. A töredékszavazatok alapján a mandátumok szétosztásáról a törvény a következőképpen rendelkezik:

\(\displaystyle a)\) Össze kell állítani egy táblázatot, amelyben minden lista neve alatt képezni kell egy számoszlopot. A számoszlop első száma az adott lista szavazatainak száma. A számoszlop következő számai az adott lista szavazatainak száma elosztva hárommal, öttel, héttel, rendre az új osztó az előző osztó kettővel megnövelt értéke.

\(\displaystyle b)\) Meg kell keresni a táblázatban előforduló legnagyobb számot, és amelyik lista számoszlopában találjuk meg azt, az a lista kap egy mandátumot. Ezt követően meg kell keresni a következő legnagyobb számot. Amelyik lista oszlopában találjuk, az a lista kap egy mandátumot. Ezt az eljárást kell folytatni mindaddig, míg kiosztásra kerül az összes mandátum.

(2010. évi L. törvény 15.§ (4))

Feladatunkban tudjuk, hogy egy adott településen hat szervezet indított jelölteket (ezek legyenek rendre A, B, C, D, E és F). Ismerjük továbbá az egyes jelölőszervezetekre jutó töredékszavazatok számát és azt, hogy összesen hány további képviselő szerezhet mandátumot. (A mintán ezeket az adatokat a szegélyezett A2:J3 tartomány tartalmazza.)

Határozzuk meg a fenti számítási mód alapján, hogy az egyes jelölőszervezetek hány főt juttathatnak be a képviselőtestületbe a kompenzációs listájukról (a minta 4. sora). Feltételes formázással emeljük ki a táblázatban a mandátumot jelentő cellákat.

Beküldendő egy tömörített i449.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. 450. A képen látható egyszemélyes ,,játékot'' bárki megvásárolhatja. A játék hat, teljesen egyforma, közös tengelyen elhelyezett ,,hengerből'' áll, amelyek palástja pontosan ugyanannyi részre oszlik. Az első, a harmadik, az ötödik és a hatodik henger minden helyen számjegyeket tartalmaz, a második műveleti jeleket, a negyedik pedig relációs jeleket. A hengereket úgy kell elforgatni egymáshoz képest, hogy a kialakuló sorok mindegyikében az első három által mutatott kifejezés és az utolsó két számjegy által alkotott szám között a negyedik helyen szereplő reláció álljon fenn.

Írjunk programot, amely a fenti játék síkbeli változatát valósítja meg. A program indításakor a játékos beállítja a sorok számát, amely 3 és 10 közötti szám lehet. Ezt követően a program véletlenszerűen generál egy kiindulási állapotot, majd megjeleníti az alábbi mintának megfelelően (bal oldali ábra). A generálásnál ügyelnünk kell arra, hogy a feladat megoldható legyen. A játék során a játékos által választott oszlopot (annak tartalmát) eggyel elcsúsztatja a többihez képest. (A kicsúszó elem az ellenkező oldalon megjelenik.) A játék befejeződik, ha a játékosnak sikerül elérnie, hogy minden sorban teljesüljön a reláció (jobb oldali ábra). A játékos a játékot feladhatja, ekkor a programnak meg kell jelenítenie a megoldást.

A feladat megoldásaként a versenykiírásban szereplő eszközökkel elkészíthető alkalmazások mellett a webes vagy mobil applikációkat is elfogadjuk.

Beküldendő egy i450.zip tömörített állományban a program forráskódja és a működéséhez szükséges egyéb fájlok, továbbá a hozzá kapcsolódó felhasználói dokumentáció, valamint a leírás, amely tartalmazza, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

Az értékelésben 7 pont jár a feladat leírásának megfelelő megoldásokért, 3 pont pedig a megoldás kifinomultsága, ötletessége, használhatósága alapján kerül kiosztásra.

(10 pont)

megoldás, statisztika


I/S-jelű feladatok

A beküldési határidő 2018. március 12-én LEJÁRT.


I/S. 24. Egy hosszú alagútban egy vágányon közlekedhetnek a vonatok egy irányban. Az érkező vonatok nem egyforma hosszúak és gyorsak, ezért az alagúton különböző idő alatt érnek át. A vonatok adott időpontban jönnek az érkezési oldalon és az alagúton való áthaladás után azonnal továbbhaladnak. Az alagútban egyszerre csak egy vonat tartózkodhat, tehát amikor az átjutott, akkor indulhat a következő. Az érkezési oldalon lévő vonatoknak így általában várakozniuk kell. Az alagút mindkét oldalán elegendő számú vágány van, tehát az érkezési oldalon megoldott a vonatok várakoztatása, illetve az alagúton történő átjutás után a kilépő vonatok megfelelő irányban való továbbhaladása. Így elvileg csak az alagút foglaltsága miatt kell várni, minden más vonatmozgás elhanyagolható ideig tart, és nem okoz fönnakadást.

A forgalomirányítók feladata megadni, hogy mikor melyik vonat haladjon át az alagúton. Ismerik minden vonat érkezési idejét, illetve tudják, hogy mennyi idő alatt halad át az alagúton. Úgy döntöttek, hogy a vonatok összes várakozási idejét minimalizálják, és ez alapján határozzák meg a vonatok áthaladási sorrendjét. Készítsünk programot, amely megoldja a forgalomirányítást.

A program standard bemenete az adott időszakban érkező vonatok \(\displaystyle N\) száma, majd a következő \(\displaystyle N\) sorban az \(\displaystyle i\)-edik vonat \(\displaystyle t_i\) érkezési és \(\displaystyle h_i\) áthaladási ideje található perc mértékegységben. Az adatok az érkezési idő szerinti sorrendben vannak. A program adja meg a standard kimenet első sorában a legkevesebb összes várakozási időt, majd a második sorában a vonatok áthaladási sorrendjét a sorszámuk fölsorolásával.

Példa (az újsor karaktereket / jelöli):

BemenetKimenet
4 / 3 10 / 5 4 / 7 4 / 8 8 /25 / 2 3 4 1 /

Korlátok: \(\displaystyle 2 \le N \le 1000\), \(\displaystyle 1\le t_i, h_i \le 10^5\), egész számok.

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle N\) érték esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy is24.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2018. március 12-én LEJÁRT.


S. 123. Egy ország sík területen fekszik, minden városa egy képzeletbeli négyzetháló egész koordinátákkal rendelkező csúcsában helyezkedik el. A közlekedési miniszter javaslatára felújítják az úthálózatot úgy, hogy minden városból minden városba el lehessen jutni. A tervek szerint a városok közötti utak az elképzelt négyzetháló élei mentén haladnának, egymással párhuzamosan, vagy egymásra merőlegesen. Az utak egy-egy egész koordinátájú pontban találkozhatnak akár egy városban, akár a városon kívül. A miniszter szeretné a legkisebb költséggel elkészíteni az új úthálózatot, ezért az utak összhosszának a lehető legkevesebbnek kell lennie. Készítsünk programot, amely megadja ezt a legkisebb értéket.

A program standard bemenete az ország városainak \(\displaystyle N\) száma, majd a következő \(\displaystyle N\) sorban az \(\displaystyle i\)-edik város helyének \(\displaystyle x_i\) és \(\displaystyle y_i\) egész koordinátái. A program adja meg a standard kimeneten az összeköttetéshez szükséges legrövidebb úthálózat teljes hosszát.

Példa (az újsor karaktereket / jelöli):

BemenetKimenet
6 / 3 2 / 9 1 / 6 5 / 2 6 / 8 7 / 5 9 /21 /

Korlátok: \(\displaystyle 2 \le N \le 1000\), \(\displaystyle 1\le x_i, y_i \le 10^5\), egész számok.

Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle N\) érték esetén ad helyes eredményt 1 másodpercen belül.

Beküldendő egy s123.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.

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