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


I. 475. Egy \(\displaystyle N\) oldalhosszúságú szabályos háromszög két fajta színű, egységnyi oldalú szabályos háromszögekből áll. Vizsgáljuk az \(\displaystyle N\) oldalhosszúságú háromszögben kirajzolódó egyszínű, szabályos háromszögeket. Készítsünk programot i475 néven, amely megadja mindkét színhez a lehető legnagyobb területű szabályos háromszög oldalának hosszát.

A program olvassa be a standard bemenet első sorából az \(\displaystyle N\) oldalhosszúságot (\(\displaystyle 1\le N\le 100\)), majd a következő \(\displaystyle N\) sorból a háromszög adott szintjén lévő egységnyi háromszögek színének kezdőbetűjét (\(\displaystyle \texttt{k}=\text{kék}\), \(\displaystyle \texttt{s}=\text{sárga}\)).

A program a standard kimenetre írja ki a kék, majd a következő sorba a sárga háromszögekből álló legnagyobb egyszínű, szabályos háromszög oldalhosszúságát.

Példa:

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

(10 pont)

megoldás, statisztika


I. 476. (É) A főváros tömegközlekedési forgalomirányítási rendszerében a járművek fedélzeti számítógépekkel rendelkeznek. Egy adott időpontban az összes jármű néhány adatát lekérdezték, amelyek rendelkezésünkre állnak a jarmu.txt, statusz.txt, tarolas.txt és a telep.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 i476 néven. A honlapunkról letölthető adatállományokat importáljuk az adatbázisba a forrásállományokkal azonos néven. Beolvasáskor állítsuk be a megfelelő adattípusokat é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 viszont ne. Megoldásainkat a zárójelben lévő néven mentsük el.

1. Soroljuk fel lekérdezés segítségével a villamosok és autóbuszok kivételével azon járművek rendszámát, típusát és fajtáját, amelyek utolsó bejelentkezése 2018. augusztus előtti. (1regi)

2. Melyik kerületben vannak a villamos járműtelepek? A listában minden kerület egyszer jelenjen meg. (2kocsiszin)

3. Lekérdezéssel határozzuk meg azoknak a járműveknek a rendszámát és típusát, amelyekhez nincs járműtelep megadva. (3hiany)

4. Adjuk meg azoknak a busz járműtelephelyeknek a név rövidítését, kerületét és címét, ahol az Ikarus egyik típusa sincs. (4nincsikarus)

5. A járműparkban van néhány olyan típus, amiből csak néhány darab van. Határozzuk meg a legkisebb darabszámú autóbusz típusát és azt, hogy az hány telephelyen van. (5keves)

6. Paraméteres lekérdezés segítségével adjuk meg a paraméterként megadott rendszámú járművel azonos napon és órában bejelentkezőket. A listában a rendszámuk, a típusuk és a fajtájuk jelenjen meg. (6egyszerre)

7. Határozzuk meg lekérdezés segítségével az oszlopok sorrendjétől eltekintve a minta szerint, hogy a fővárosban melyik járműfajtából hány darab jármű van. (7osszesites)

Beküldendő egy tömörített i476.zip állományban az adatbázis, valamint egy rövid dokumentáció, amely megadja az alkalmazott adatbázis-kezelő nevét és verziószámát.

Letölthető fájlok: jarmu.txt , statusz.txt , tarolas.txt , telep.txt.

(10 pont)

megoldás, statisztika


I. 477. A bal oldali képen látható egyszemélyes játék egyszerűbb változatát mutatja a jobb oldali kép.

Az egyszerűsített forma négy egymásba fonódó körből áll, amelyek mentén egymástól egyenlő távolságra egy-egy kör került elhelyezésre a minta szerint. Mindegyik kör – egymástól függetlenül – \(\displaystyle 60^\circ\)-kal elforgatható, természetesen egyszerre csak egy. A forgatás az éppen rajta lévő kis köröket ,,magával viszi'', így néhány forgatás után a kezdetben rendezett színösszeállítás (a kisebb körök mentén 6, azonos színű kör van) már igen nagy összevisszaságot mutathat.

A feladatunk a síkbeli változat grafikus megvalósítása. A használó választhasson: a rendezett állapotból indulva szabadon használja a játékot, vagy kérhet egy véletlenszerű (de megoldható) állapotot, amelyből indulva előállíthatja a rendezett állapotot. (Rendezett állapotnak azt tekintjük, ha a kis körök mentén egyező színek vannak, függetlenül azok elhelyezkedésétől.)

A feladat megoldását a versenykiírásban szereplő eszközökön túl a webböngészőben, vagy mobil eszközökön futó applikációval is meg lehet adni. A feltétel, hogy a megoldás tesztelhető legyen Windows, Linux vagy Android alapú operációs rendszer alatt ingyenes eszközökkel, kiegészítők telepítése nélkül.

Beküldendő egy i477.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ő környezetben fordítható. Szükség esetén a tesztkörnyezetet is pontosan meg kell adni.

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 történő differenciálásra szolgál.

(10 pont)


I/S-jelű feladatok

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


I/S. 33. Egy adatsokaságban \(\displaystyle N\) féle adat van. Tudjuk minden adatról, hogy hányszor szerepel az adatsokaságban, és tudjuk azt is, hogy egy adott típusú adat törlése vagy beszúrása mennyibe kerül. Adjuk meg minden adattípusra, hogy minimum milyen költséggel érhető el adatok törlésével és beszúrásával, hogy ez az adattípus (is) az adatsokaság módusza legyen.

Bemenet: az első sorban az adattípusok \(\displaystyle N\) száma szerepel. A második sorban \(\displaystyle N\) darab szám: az \(\displaystyle i\). szám azt mondja meg, hogy az \(\displaystyle i\). adattípus hányszor szerepel az adatsokaságban. A harmadik sorban \(\displaystyle N\) darab szám van: az \(\displaystyle i\). szám azt mondja meg, hogy az \(\displaystyle i\). adattípusú adat beszúrása vagy törlése mennyibe kerül.

Kimenet: egy sorba írjunk ki \(\displaystyle N\) darab számot: az \(\displaystyle i\). szám annak a minimális költsége, ami szükséges ahhoz, hogy az \(\displaystyle i\). adattípus módusz legyen.

Példa:

Korlátok: \(\displaystyle 2\le N\le {10}^{5}\), \(\displaystyle 0\le \text{a}\) 2. és 3. bemeneti sorban levő \(\displaystyle \text{számok} \le {10}^{9}\). Időlimit: 0,5 mp.

Értékelés: a pontok 20%-a kapható, hogyha \(\displaystyle N\le 100\), a 2. és 3. bemeneti sorban levő \(\displaystyle \text{számok}\le 100\); további 10% kapható, ha a 2. sor számai egyenlők; további 20% kapható, ha \(\displaystyle N\le 1000\); további 10% kapható, ha a 2. és 3. bemeneti sorban levő \(\displaystyle \text{számok}\le {10}^{6}\); további 40% kapható az eredeti korlátokra.

Beküldendő egy is33.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.

(10 pont)


S-jelű feladatok

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


S. 132. Egy ország \(\displaystyle N\) városa között az elektromos energiát vezetékeken szállítják. Minden vezeték két várost köt össze, elektromos energiát előállító erőmű csak a 0 indexű városban van. Két várost több vezeték is összeköthet. Egy város akkor kap áramot, ha a vezetékekkel közvetlenül vagy közvetetten összeköttetésben van az erőművel. Egy vezeték nélkülözhetetlen, ha meghibásodásakor lesz olyan város, ami nem kap áramot.

Az országnak túl költséges karbantartani az összes vezetéket, ezért úgy döntenek, hogy \(\displaystyle Q\) darab vezetéket eltávolítanak a hálózatból. Kíváncsiak vagyunk, hogy kezdetben hány nélkülözhetetlen vezeték van, és hogy az egyes vezetékek eltávolításával mennyivel nő a nélkülözhetetlen vezetékek száma. A vezetékek eltávolítása során sosem lesz olyan város, ami nem kap áramot.

Bemenet: az első sorban a városok \(\displaystyle N\) száma, a vezetékek \(\displaystyle M\) száma és az eltávolítandó vezetékek \(\displaystyle Q\) száma található. A városokat és vezetékeket is 0-tól indexeljük. A következő \(\displaystyle M\) sor mindegyike két város indexét tartalmazza, amiket összeköt az adott vezeték. Az utolsó \(\displaystyle Q\) sor mindegyike egy vezeték indexét tartalmazza, amit eltávolítanak.

Kimenet: Az első sorba írjuk ki, hogy kezdetben hány nélkülözhetetlen vezeték van. A következő \(\displaystyle Q\) sorba pedig azt, hogy az egyes vezetékek eltávolításával mennyi lesz a nélkülözhetetlen vezetékek száma.

Példa:

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle N-1\le M\le {10}^{6}\), \(\displaystyle 0\le Q\le {10}^{5}\). Időlimit: 0,5 mp.

Értékelés: a pontok 20% kapható, ha \(\displaystyle Q=0\)-ra ad jó megoldást; további 20%, ha \(\displaystyle Q\cdot M\le {10}^{6}\); további 10%, ha az eltávolítások során végig maximum 2 nélkülözhetetlen vezeték van; további 50% az eredeti bemenetre.

Beküldendő egy s132.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.

(10 pont)


Figyelem!

Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.