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. 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ő: 2019. október 10.. 24:00 (UTC+01:00).


I. 487. Adott egy \(\displaystyle N\) elemű, pozitív egészekből álló számhalmaz (\(\displaystyle 2\le N\le 20\)). Készítsünk programot, amely

\(\displaystyle a)\) megkeresi a legnagyobb olyan \(\displaystyle a\) számot a halmazban, amely minden nála kisebb halmazbeli számhoz relatív prím;

\(\displaystyle b)\) megadja a legkisebb olyan \(\displaystyle a\)-nál nagyobb \(\displaystyle b\) számot, amellyel kibővítve a halmazt az \(\displaystyle a)\) feladatrész megoldása a hozzávett \(\displaystyle b\) szám lesz – illetve 0-t ad, ha nincs ilyen \(\displaystyle b\) szám.

A program a standard bemenet első sorából olvassa be \(\displaystyle N\) értékét, majd a következő sorból a halmazt alkotó \(\displaystyle N\) darab egész számot. A standard kimenet első sorába írja az \(\displaystyle a)\) feladatrészben keresett számot, a kimenet második sorába a \(\displaystyle b)\) feladatrész megoldását.

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

Letölthető állomány: i487beki.zip

(10 pont)


I. 488. A biológiai kísérletek kiértékelését igyekeznek automatizálni. Egy négyzet alakú táptalajon tenyésztett baktériumtörzs példányait lefényképezik, majd a fotókat több lépésben digitálisan feldolgozzák. A baktériumpéldányok különböző méretűek, alakúak és helyzetűek.

A táptalaj fényképét egy képzeletbeli négyzetháló segítségével cellákra osztják. Egy \(\displaystyle 50\times 50\) cellából álló, az egyes baktériumpéldányokat már számokkal azonosítottan megjelenítő táblázat áll rendelkezésre a meres.txt tabulátorral tagolt, UTF-8 kódolású állományban.

A baktériumok az előfeldolgozott képen 1 és \(\displaystyle N\) közötti egész számmal (\(\displaystyle N\le 50\)) vannak azonosítva. Egy-egy példány összefüggő területet alkot, de egy cella csak egy baktériumhoz tartozik. Ha egy cellában nincs baktérium, akkor ott a táblázatban nincs adat. A mintán két baktériumpéldány látható, az 1-es és a 4-es sorszámú.

Értékeljük ki és segítsük a további munkát táblázatkezelővel.

1. Töltsük be a meres.txt szövegfájlt a táblázatkezelő egy munkalapjára az A1-es cellától kezdődően. A munkalap neve legyen kep. Munkánkat bakterium néven mentsük el a táblázatkezelő alapértelmezett formátumában.

2. Hozzunk létre még két munkalapot szamolas és eredmeny néven. A szamolas munkalapon végezzünk el minden, a megoldáshoz szükséges számolást. Az eredmeny munkalapon jelenítsük meg a kérdésekre adott válaszokat és eredményeket. Mind a két munkalap tartalmának értelmezését feliratokkal segítsük.

3. A kep munkalapon az A:AX oszlopok szélességét és az 1:50 sorok magasságát állítsuk be úgy, hogy a cellák (normál nézetben) négyzetek legyenek.

4. A mérési eredményeket szemléltessük feltételes formázással. A különböző baktériumpéldányok celláit más-más kitöltőszínnel jelenítsük meg, az üres cellák maradjanak fehérek.

5. Ha az eredmeny munkalap egy adott cellájába beírunk egy sorszámot 1 és 50 között, akkor a mellette lévő cellában jelenjen meg, hogy ilyen sorszámú baktérium szerepel-e a képen.

6. Adjuk meg, hogy összesen hány baktérium van a képen.

7. Adjuk meg, hogy hányas sorszámú baktérium foglalja el a legnagyobb területet a képen és ez hány cella.

8. Adjuk meg annak a minimális méretű téglalapnak a szélességét és magasságát, amelyben a képen látható összes baktérium benne van.

9. Ha van, akkor adjuk meg két érintkező baktérium sorszámát, ha nincs, akkor írjuk ki, hogy ,,Nincsenek egymással érintkező baktériumok.''

Beküldendő egy tömörített i488.zip állományban a munkafüzet, valamint egy rövid leírás, amelyben szerepel az alkalmazott táblázatkezelő neve és verziószáma.

Letölthető állomány: meres.txt

(10 pont)


I. 489. (É). Tamás a kedvenc fényképeit rendezgette. Ezek mindegyikén szerepelnek emberek, akiket a programban egy ékezetek nélküli keresztnév vagy megszólítás azonosít. Előfordulnak a képeken Tamás és családtagjai (őket a programban az En, Apa, Anya, Mama, Papa, Ocsi, Hugi szöveggel jelöljük), valamint Tamás barátai, osztálytársai (a programban például Anna, Zsolt, Judit, Evi). Minden képen legalább egy személy szerepel, de egy képen természetesen egy személy csak egyszer. A képeken csak ismert, azonosítóval rendelkező személyek láthatók, minden azonosító egy szóból áll.

A képek némelyikéről tudni lehet, hogy hol vagy milyen alkalommal készült, melyeket a programban szintén ékezetek nélkül azonosítunk, például Otthon, Erdei_suli, Tisza-to (a többszavas neveket aláhúzásjellel kapcsoltuk össze). Sok esetben szerepel a képen a felvétel időpontja, például 2017.3.18.

A képek készítésének helye, ideje és a rajta szereplő személyek megtalálhatóak a kepszem.txt szöveges állományban. A hiányzó időpont vagy helyszín helyett egy (`-') kötőjel szerepel a megfelelő helyeken.

A fájl első sorában a képek \(\displaystyle K\) száma (\(\displaystyle 5 \le K \le 100\)), és a következő \(\displaystyle K\) sorban egy-egy kép adatai találhatók az alábbi minta szerint.

40
Szeged 2016.11.21. Juli Ocsi En
Fociedzes - Mama Ivan En Szabolcs
Otthon 2012.8.8. Szasa Laci Andras Hanna Zsuzsi Benedek Marci
...

Készítsünk programot, amely beolvassa a szöveges állományból az adatokat, és azok földolgozásával megoldja a következő feladatokat. Minden feladat be- és kimenete előtt írjuk ki a feladat sorszámát egy külön sorba a következő formában ,,3. feladat:''.

1. Adjuk meg, hogy Tamás hány ismerőse szerepel a képeken. Az eredmény például a következő szöveg legyen: ,,Tamasnak 27 ismerose szerepel a kepeken.''.

2. Határozzuk meg, hogy hány olyan kép van, ahol nem ismert a készítés helye és időpontja sem. Az eredményt a következőképp írjuk ki: ,,6 kep keszitesenek ideje es helye ismeretlen.''.

3. Adjuk meg, hogy hányan szerepelnek azon a képen, ahol a legtöbb személy fordul elő. A kiírás a következők szerint történjen: ,,12 embernel nincs több egy kepen sem.''.

4. Írjuk ki a képeken szereplő összes személy azonosítóját ABC-sorrendben egy sorban, vesszővel elválasztva és ponttal a végén. A kiírás formája: ,,A kepeken szerepel: Anna, Balazs, Cecil ...''.

5. Kérjük be az egyik ismerős nevét, és adjuk meg azokat az ismert időpontokat (az adatfájlban adott sorrendben), amikor Tamás (azonosítója En) és a bekért személy a fényképek szerint együtt volt. A bekérés formája: ,,Kerem adj meg egy szereplot: Ocsi''. Az eredményt a következőképp írjuk ki: ,,Tamas es Ocsi kozos idopontjai: 2019.5.10. 2020.7.7.'' Ha nincs közös időpont, akkor a ,,Tamas es Ocsi nem szerepel kozosen ismert idopontban keszitett kepen.'' mondatot írjuk ki.

6. Tamás szeretne egy családi tablót készíteni, ezért összegyűjti azokat a képeket, amelyeken legalább két, Tamáson kívüli családtag szerepel (hogy Tamás szerepel-e vagy sem, az nem lényeges). Készítsünk egy listát ezekről a képekről úgy, hogy megadjuk a készítés helyét, a készítés idejét, valamint a családtagok azonosítóját. A listában a képek legyenek az adatfájlban szereplő sorrendben, az egyes képen szereplő személyek ABC-sorrendben.

A lista formája legyen a következő (az adatokat táblázatosan jelenítsük meg, az első két oszlop szélessége 16-16 karakter):

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

Letölthető állomány: i489forrasbeki.zip

(10 pont)


I/S-jelű feladatok

A beküldési határidő: 2019. október 10.. 24:00 (UTC+01:00).


I/S. 37. Béla a titkosszolgálatnak dolgozik, feladata egy szuperintelligens idegen civilizáció által küldött üzenetek feldolgozása. Az üzentek \(\displaystyle N\) hosszú jelsorozatok, melyek `0'-t és `1'-et tartalmaznak. Mivel ez egy nem túl izgalmas munka, Béla úgy döntött megkeresi a számára érdekes részeket az üzenetben. Bélának az üzenet azon részei érdekesek, melyek `00'-val kezdődnek és `11'-gyel végződnek. Segítsünk Bélának megmondani, hogy mennyi érdekes része van az üzenetnek, vagyis hány olyan \(\displaystyle x\); \(\displaystyle y\) (\(\displaystyle x< y\)) számpár van, amelynél az üzenet \(\displaystyle x\)-edik és \(\displaystyle (x+1)\)-edik helyén `0', \(\displaystyle y\)-adik és \(\displaystyle (y+1)\)-edik helyén `1' szerepel.

Standard bemenet: az első és egyetlen sora tartalmazza az üzenetet.

Standard kimenet: az első sora tartalmazza az érdekes részek számát.

Korlátok: \(\displaystyle 1\le N\le {10}^{5}\), időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható \(\displaystyle N\le {10}^{4}\) esetén.

Példa:

BemenetKimenet
100010110114

Beküldendő egy is37.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ő: 2019. október 10.. 24:00 (UTC+01:00).


S. 136. Adott egy \(\displaystyle N\) csúcsú, \(\displaystyle M\) élű egyszerű gráf (nincs többszörös él vagy hurokél, de nem feltétlenül összefüggő). A csúcsokat 0-tól \(\displaystyle (N-1)\)-ig indexeljük. A gráf összes csúcsa fekete vagy fehér. Jelölje \(\displaystyle f(x)\) az \(\displaystyle X\) csúcs színét. Cseresznyének hívunk egy \(\displaystyle (A,B,C)\) rendezett csúcshármast, ha páronként különbözőek és létezik az \(\displaystyle A-B\), valamint a \(\displaystyle B-C\) csúcspárok közt él. Egy \(\displaystyle (A,B,C)\) cseresznye finom, ha \(\displaystyle f(A)=f(C)\) és \(\displaystyle f(A)\ne f(B)\). Adjuk meg, hogy egy él behúzásával legföljebb mennyire növelhető a finom cseresznyék száma. (\(\displaystyle A\) és \(\displaystyle B\) csúcs összeköthető egy éllel, ha \(\displaystyle A\ne B\), és eddig nem létezett köztük él.)

Standard bemenet: az első sor tartalmazza \(\displaystyle N\)-et és \(\displaystyle M\)-et. A következő sor \(\displaystyle N\) darab számot tartalmaz: az \(\displaystyle i\)-edik szám az \(\displaystyle i-1\) indexű csúcs színét határozza meg, 0 ha fekete, 1 ha fehér. A következő \(\displaystyle M\) sor mindegyike két számot tartalmaz. Az \(\displaystyle i\)-edik sor az \(\displaystyle i\)-edik él két végpontjának csúcsindexét adja meg.

Standard kimenet: a maximálisan elérhető finom cseresznyék száma.

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 0\le M\le \min (10^{5},N^{2}-N-1)\). Időkorlát: 0,3 mp.

Értékelés: A pontok 50%-a kapható, ha a gráf fa.

Példa:

Bemenet (a / jel sortörést helyettesít)Kimenet
5 4
0 1 1 1 0
0 1 / 1 4 / 3 0 / 0 2
12
Beküldendő egy s136.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.