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 2020. októberi 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ő 2020. november 16-án LEJÁRT.


I. 517. Bűvös négyzetnek nevezzük az \(\displaystyle N\times N\) darab szám négyzetes elrendezését, amelyben minden sor, minden oszlop és mind a két átló összege ugyanaz a szám. Az ördögkeret olyan bűvös négyzet, amelynek a legkülső keretét elhagyva is bűvös négyzetet kapunk. Lehetséges, hogy egy ördögkeretben több koncentrikus bűvös négyzet van egymásba ágyazva, ilyenkor a bűvös négyzet külső kereteit elhagyva végül egy olyan belső elrendezéshez jutunk, amely már nem bűvös négyzet.

3 mélységű ördögkeret

Készítsünk programot i517 néven, amely egy \(\displaystyle N\times N\) számból álló négyzetről meghatározza, hogy milyen mélységben tartalmaz bűvös négyzeteket egymásba ágyazva. Ha ez a szám 0, akkor már a kiinduló elrendezés sem volt bűvös négyzet.

A program standard bemenetének első sorában az \(\displaystyle N\) (\(\displaystyle N\le 30\)) található, amely a sorok és oszlopok száma. A következő \(\displaystyle N\) sorban \(\displaystyle N\) darab nemnegatív szám szerepel.

A program standard kimenetén egy szám szerepeljen, az ördögkeret egymásba ágyazott bűvös négyzeteinek mélysége. Ha a kiindulási állapot nem bűvös négyzet, akkor 0-t írjunk ki.

Beküldendő egy tömörített i517.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)


I. 518. Az egész számok számrendszerek közötti átváltására létezik algoritmus, így nem nehéz programot készíteni egy \(\displaystyle R\) alapú számrendszerben felírt \(\displaystyle A\) pozitív egész szám \(\displaystyle Q\) alapú számrendszerbe való átírására. Nehézséget talán csak a 10-nél nagyobb alapú számrendszerek jelentenek, ahol a 10-nél nagyobb számjegyeket pl. betűkkel kell jelölnünk. Az informatikában használt hexadecimális számrendszerben a \(\displaystyle 10=\mathrm{A}\), \(\displaystyle 11=\mathrm{B}\), \(\displaystyle \ldots\), \(\displaystyle 15=\mathrm{F}\) jelölést alkalmazzuk. Használjuk ennek megfelelően az angol ABC nagybetűit rendre a 9-nél nagyobb számjegyek jelölésére. Így a legnagyobb számjegy, amit felírhatunk, a \(\displaystyle \mathrm{Z}=35\).

Készítsünk táblázatkezelő alkalmazást, amely átvált egy pozitív egész számot az \(\displaystyle R\) alapú számrendszerből a \(\displaystyle Q\) alapú számrendszerbe (\(\displaystyle 2\le R,Q\le 36\)). A munka­lapon egy cellában lehessen megadni az átváltandó számot (számjegyekkel és az angol ABC betűivel), és két másik cellában az \(\displaystyle R\) és \(\displaystyle Q\) értékét. A táblázatkezelő adja meg egy negyedik cellában a szám alakját a \(\displaystyle Q\) alapú számrendszerben.

A munkafüzet tetszőleges további cellái használhatók segédszámításokra, de a megoldás során csak a táblázatkezelő beépített függvényeivel dolgozzunk, tehát makró és saját program a megoldás során nem használható. A beírt számok minden esetben helyesek, azok ellenőrzéséről nem kell gondoskodni.

Beküldendő egy tömörített i518.zip állományban a megoldást tartalmazó táblázatkezelő munkafüzet és egy rövid dokumentáció, amely megadja az alkalmazott táblázatkezelő nevét és verzióját.

(10 pont)


I. 519. (É.) A www.balatonihajok.hu portálról sok olyan balatoni hajózásra jellemző adatot ismerhetünk meg, amely történetileg és a jelenben is érdekes lehet. Most a nagy hajós kikötőkkel foglalkozunk. Az adatok a kikoto.txt, a kapcsolo.txt és a tipus.txt állományokban állnak rendelkezésünkre. 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 balaton néven. A mellékelt adatállományokat importáljuk az adatbázisba a fájlnévvel azonos táblanéven (kikoto, kapcsolo, tipus). Beolvasáskor állítsuk be a megfelelő adatformátumokat é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. A megoldásainkat a zárójelben lévő néven mentsük el.

1. A Balatonon a legnagyobb sebességű szelek északi irányból érkeznek. A déli parton úgy építették a kikötőket, hogy tisztán északról védve legyenek, a bejáratok északnyugatra, vagy északkeletre nézzenek. Készítsünk lekérdezést, amely az ,,É'' szórészletet tartalmazó bejáratú kikötők nevét és bejáratának irányát megjeleníti nyugatról keletre sorrendben. (1eszak)

2. Készítsünk lekérdezést, amely történetileg az első három kiépített kikötő nevét sorolja fel. (2regiek)

3. Adjuk meg lekérdezés segítségével az egymólós, a kétmólós és karolómólós (kőszórás a kikötő körül védelmi célból) kikötők számát. (3molok)

4. Lekérdezés segítségével soroljuk fel a Balaton nyugati medencéjének kikötőit, azaz a Tihanyi kikötőtől nyugatra lévőket. (4nyugat)

5. Lekérdezés segítségével soroljuk fel a mólóval nem rendelkező, azaz nem védett kikötők nevét. A listában minden név egyszer jelenjen meg. (5vedtelen)

6. A nyílt vízi kikötőknél nincs értelme a terület megadásának, de a többinél jellemző adat. Adjuk meg lekérdezés segítségével azon kétmólós és medencés kikötők nevét, ahol mégsem ismert a terület. (6adathiany)

7. Lekérdezés segítségével adjuk meg az egymástól legtávolabbi két kikötőt. Távolságon a feladatban a Manhattan-távolságot értjük. A távolság meghatározásához használjuk a kikötők szélességi és hosszúsáig GPS-koordinátáit. (7tavolsag)

Beküldendő egy tömörített állományban (i519.zip) az adatbázis, valamint egy rövid dokumentáció, amelyből kiderül az alkalmazott adatbázis-kezelő neve és verziószáma.

Letölthető állományok: kikoto.txt, kapcsolo.txt, tipus.txt.

(10 pont)


I/S-jelű feladatok

A beküldési határidő 2020. november 16-án LEJÁRT.


I/S. 47. Adél és Bence a következő játékot játsszák: Adél rajzol egy \(\displaystyle N\) szélességű és \(\displaystyle N\) magasságú egységoldalú négyzetekből álló négyzethálót, majd minden mezőbe beír egy egész számot. Ezután Bence választ egy \(\displaystyle K\) pozitív egész számot, és rajzol egy \(\displaystyle 3\cdot 3\) db, \(\displaystyle K\) oldalhosszú négyzetekből álló hálót úgy, hogy \(\displaystyle 3K\le N\) legyen. Ezután a saját \(\displaystyle K\) oldalú négyzetei közül kiszínez tetszőlegesen \(\displaystyle X\) darabot (\(\displaystyle 1\le X\le 9)\), majd a saját mintáját ráilleszti a számozott négyzetrácsra úgy, hogy szélei a rácsvonalakra illeszkedjenek és a minta ne lógjon le a négyzetrácsról. Bence pontszáma a színezett terület által lefedett mezőkben lévő számok összege. Adjuk meg, hogy legföljebb hány pontot szerezhet Bence.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) számot. A következő \(\displaystyle N\) sor mindegyike \(\displaystyle N\) számot tartalmaz, a mezőkbe írt számokat. Az \(\displaystyle i\)-edik sor \(\displaystyle j\)-edik eleme \(\displaystyle A_{i,j}\).

Kimenet: az elérhető legnagyobb pontszám.

Példa:

Korlátok: \(\displaystyle 3\le N\le 100\), \(\displaystyle -1000\le A_{i,j}\le 1000\), Adél biztosan írt nemnegatív számot. Időkorlát: 0,5 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 10\).

Beküldendő egy is47.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ői környezetben futtatható.

(10 pont)


S-jelű feladatok

A beküldési határidő 2020. november 16-án LEJÁRT.


S. 146. Adott egy \(\displaystyle N\) elemű \(\displaystyle T\) tömb 1-től indexelve, amely nemnegatív egész számokat tartalmaz. Kétféle műveletet végzünk a \(\displaystyle T\) tömb elemeivel. Az egyik műveletben hozzáadunk a tömb néhány egymást követő eleméhez egy \(\displaystyle p\) értéket, vagyis adott \(\displaystyle a\) és \(\displaystyle b\) mellett minden \(\displaystyle i\in [a,b]\) indexű \(\displaystyle T[i]\) elem ezután \(\displaystyle T[i]+p\) lesz. Definiáljuk adott \(\displaystyle c\) és \(\displaystyle d\) esetén (ahol \(\displaystyle d-c+1\) páros) a következő szorzatösszeget: \(\displaystyle T[c]\cdot T[c+1] + T[c+2]\cdot T[c+3] + \ldots + T[d-1]\cdot T[d]\), amely a \(\displaystyle [c,d]\) intervallum értéke a \(\displaystyle T\) tömbön. A második műveletben adjuk meg a \(\displaystyle c\) és \(\displaystyle d\) számok által meghatározott intervallum értékét. Mivel egy intervallum értéke nagyon nagy is lehet, ezért a lekérdezés eredményének \(\displaystyle {10}^{9}+7\)-tel vett osztási maradékát kell megadni.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) és \(\displaystyle Q\) számokat. A következő sor \(\displaystyle N\) számot tartalmaz, \(\displaystyle T\) elemeit. A következő \(\displaystyle Q\) sor mindegyike vagy \(\displaystyle 1\ a\ b\ p\) alakú, ami azt jelenti, hogy az \(\displaystyle [a;b]\) intervallumon minden tömbértéket megváltoztatunk \(\displaystyle p\)-vel; vagy \(\displaystyle 2\ c\ d\) alakú, ami azt jelenti, hogy lekérdezzük a \(\displaystyle [c,d]\) intervallum értékét.

Kimenet: minden 2-es típusú kérdésre adjuk meg az intervallum értékét modulo \(\displaystyle {10}^{9}+7\).

Példa:

Korlátok: \(\displaystyle 1\le N,Q\le {10}^{5}\), \(\displaystyle 0\le T[i],p\le {10}^{9}\), \(\displaystyle 1\le a,b,c,d\le N\), \(\displaystyle a\le b\), \(\displaystyle c<d\). Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 100\).

Beküldendő egy s146.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ői 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.