A KöMaL 2025. áprilisi informatika feladatai

I-jelű feladatok A beküldési határidő 2025. május 15-én LEJÁRT.

---

I. 659. Egy téglalap alakú asztalon robotjárművek mozognak úgy, hogy időegységenként egységnyi távolságot tesznek meg. Minden járművet úgy indítunk el, hogy az asztal valamelyik szélével párhuzamosan mozogjon. A járművek szenzora érzékeli az asztal szélét, így ott a mozgás iránya az ellenkezőjére vált. Előfordulhat, hogy egy idő után két jármű összeütközne, de ilyenkor a szenzor érzékelése alapján a két jármű megáll.

Készítsünk programot i659 néven, amely megadja, hogy \(\displaystyle T\) időegység alatt mikor áll meg először két robotjármű.

A program standard bemenetének első sorában az asztal oldalainak hossza (\(\displaystyle {1\leq N,\;M\leq 100}\)), a robotjárművek száma (\(\displaystyle 1\leq DB\leq 10\)) és a vizsgált időtartam (\(\displaystyle {1\leq T\leq 1000}\)) található. A következő \(\displaystyle DB\) sor egy-egy jármű indulási helyét (\(\displaystyle {1\leq X_{i}\leq N}\), \(\displaystyle 1\leq Y_{i}\leq M\)) és mozgásának irányát tartalmazza (F, L, J, B – fel, le, jobbra, balra, ahol fel és le az egyik oldallal párhuzamos, míg a jobbra és balra az ezekre merőleges irányú mozgásirányt jelenti).

A programmal a standard kimenetre írjuk ki, hogy az ütközés elkerülése miatt mikor áll meg az első két robotjármű. Ha \(\displaystyle T\) időegység alatt nincs ilyen esemény, akkor \(\displaystyle {-1}\)-et írjunk ki.

Példa:

Magyarázat: a robotok kezdeti helyzete és iránya látható az alábbi ábrán. Négy időegység után a 2. sor 7. cellájában ütközne két robot.

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

megoldás, statisztika

---

I. 660. Nevezzük \(\displaystyle K\)-nak az origó középpontú, \(\displaystyle 10\;000\) egység sugarú körlap I. síknegyedbe eső részét. Matematikai formalizmussal: az \(\displaystyle x\geq 0\) és \(\displaystyle y\geq 0\) és \(\displaystyle x^2+y^2\leq 10\;000^2\) feltételekkel adott ponthalmaz.

Feladataink:

1. Nyissunk meg egy üres táblázatkezelő munkafüzetet, nevezzük át a munkalapot negyedkor névre, a munkafüzetet mentsük pontok néven. Segédszámításokat csak ezen a munkalapon végezzünk a 9. sor alatt.
2. Hozzunk létre egy üres munkalapot segedadatok néven. Illesszük be az A1 cellától az UTF-8 kódolású, tabulátorokkal tagolt segedadatok.txt fájl tartalmát és formázzuk meg a minták szerint:



Számítsuk ki a választ a következő kérdésekre és jelenítsük meg az eredményt a zárójelben jelölt cellában:

1. Hány rácspont (vagyis olyan pont, amelynek mindkét koordinátája egész szám) van \(\displaystyle K\) belsejében? (A1)
2. Hány olyan rácspont van \(\displaystyle K\) belsejében, amelyiknek mindkét koordinátája négyzetszám? (A2)
3. Hány olyan rácspont van \(\displaystyle K\) belsejében, amelyiknek mindkét koordinátája köbszám? (A3)
4. Hány olyan rácspont van \(\displaystyle K\) belsejében, amelyiknek mindkét koordinátája prímszám? (A4)
5. Hány olyan rácspont van \(\displaystyle K\) belsejében, amelyiknek x koordinátája prímszám, \(\displaystyle y\) koordinátája négyzetszám? (A5)
6. Melyik az a legkisebb, egész értékű r sugár, amely esetén a \(\displaystyle K\)-hoz hasonlóan elhelyezkedő \(\displaystyle r\) sugarú \(\displaystyle k\) negyedkör belsejében a fenti első négy feltételnek eleget tevő pontokból mind a négy feltétel esetén legalább \(\displaystyle 100\)-\(\displaystyle 100\) pont van? (A6)

Segédszámításokat a negyedkor munkalapon a 9. sor alatt lehet végezni. A megoldásban saját függvény vagy makró nem használható.

Beküldendő az i660.zip tömörtett állományban a munkafüzet és egy rövid dokumentáció, amelyben szerepel a számítások magyarázata, a táblázatkezelő neve és verziószáma.

Letölthető fájl: segedadatok.txt

(10 pont)

megoldás, statisztika

---

I. 661. A szeptemberi számban megjelent I. 633. feladat és a novemberi számban megjelent I. 641. feladat harmadik része következik. Most ötféle speciális prímet keresünk az első százezer prímszám között, ezek a kiegyensúlyozott prímek, a prímnégyesek, a biztonságos prímek, a szuper prímek és az unokatestvér prímek. Nézzük is ezek definíciót:

Kiegyensúlyozott prímnek nevezzük azt a \(\displaystyle p\) prímszámot, amely azonos távolságra van a két szomszédos prímtől. Például a \(\displaystyle 3637\) ilyen prím, a két szomszédos prímszám: 3761 és 3641.

Prímnégyesnek nevezzük a \(\displaystyle p\), \(\displaystyle p+2\), \(\displaystyle p+6\), \(\displaystyle p+8\) számnégyest, ha mind a négy szám prím. Például: a \(\displaystyle (9431; 9433; 9437; 9439)\) ilyen számnégyes, hiszen a \(\displaystyle 9431\), a \(\displaystyle 9433\), a \(\displaystyle 9437\) a \(\displaystyle 9439\) szám is prímszám.

Biztonságos prímnek azt a \(\displaystyle p\) prímet nevezzük, amelynél \(\displaystyle \frac{p-1}{2}\) is prím. Például: az \(\displaystyle 1319\) ilyen prím, hiszen az eggyel kisebb \(\displaystyle 1318\) fele \(\displaystyle 659\), amely szintén prímszám.

Szuperprímek azok a prímek, amelyeknek a prímszámok sorozatában vett indexe is prímszám. Például: a \(\displaystyle 67\), amely a \(\displaystyle 19\). prímszám vagy az \(\displaystyle 547\), amely a \(\displaystyle 101\). prímszám, és – persze – a 19 és a 101 is prím.

Unokatestvér prímeknek az olyan prímszám-párokat nevezzük, amelyek különbsége \(\displaystyle 4\). Tehát \(\displaystyle p\) és \(\displaystyle p+4\) is prím. Például unokatestvér prímek a \(\displaystyle 757\) és \(\displaystyle 761\) vagy a \(\displaystyle 175\;753\) és a \(\displaystyle 175\;757\) prímszámok.

1. Egy üres táblázatkezelő munkafüzetben nevezzük át a munkalapot primek névre, a munkafüzetet mentsük prim_3-resz néven.
2. Illesszük be az A3 cellától az első \(\displaystyle 100\;000\) prím listáját a 100000prim.txt fájlból. Az első két sorba oszlopfeliratok kerülhetnek a számításokhoz.
3. Válogassuk ki az öt prímcsoport első \(\displaystyle 100\;000\) prím közé eső tagjait. A számításokat ezen a munkalapon végezzük.
4. Hozzunk létre egy eredmények nevű munkalapot, amelynek A oszlopát töltsük fel számokkal \(\displaystyle 1\)-től addig, amennyi a speciális prímszámok darabszámának maximuma. A következő oszlopokban határozzuk meg:
1. A B oszlopban a kiegyensúlyozott prímeket növekvő sorrendben, helykihagyás nélkül. A C oszlopban az adott kiegyensúlyozott prím távolságát a szomszédaitól.
2. A \(\displaystyle \textbf{D}\,\textbf{:}\,\textbf{G}\) oszlopban a prímnégyeseket, a D oszlopba kerülők növekvő sorrendjében, helykihagyás nélkül.
3. A H és I oszlopban a biztonságos prímeket és a kisebb párjukat növekvő sorrendben, helykihagyás nélkül.
4. A J oszlopban a talált szuperprímeket növekvő sorrendben, helykihagyás nélkül.
5. A \(\displaystyle \textbf{K}\,\textbf{:}\,\textbf{L}\) oszlopba pedig az unokatestvér prímek kerüljenek (a K oszlopba a kisebb unokatestvér) növekvő sorrendben, helykihagyás nélkül.
5. A munkalap adattartományát formázzuk a minta szerint.



6. Számoljuk össze, hogy ezer prímenként hány szám fordul elő az öt kategóriában (a prímnégyeseknél és az unokatestvér prímeknél a legkisebb értéket számolva). Határozzuk meg az öt kategóriában az adatok szórását és ábrázoljuk oszlopdiagramon a legnagyobb szórású adatsor adatait a max nevű, diagram elrendezésű munkalapon. A diagram címében a prímcsoport neve szerepeljen, ezt kövesse a ,,számok előfordulása 1000 prímenként'' szöveg.
7. Az eredmények munkalapon cseréljük le oszloponként az első tíz sor utáni képleteket az értékükre.
8. Végül a munkafüzetet mentsük az eredeti nevén xlsb formátumban (bináris munkafüzetként).

Segédszámításokat a primek munkalapon végezhetünk. A megoldásban saját függvény vagy makró nem használható.

Beküldendő az i661.zip tömörtett állományban a munkafüzet és egy rövid dokumentáció, amelyben szerepel a táblázatkezelő neve, verziószáma.

Letölthető fájl: 100000prim.txt

(10 pont)

megoldás, statisztika

---

I. 662. Nagy méretű táblázatokban adatok elhelyezésére és gyors keresésére sok esetben hash-, vagy más néven hasítófüggvényeket alkalmaznak. Az eljárás egy lehetséges módja a következő: a legföljebb \(\displaystyle N\) számú adatnak \(\displaystyle N+M\) méretű tömböt foglalunk le, majd megadunk egy olyan hash-függvényt, amely az adat tulajdonságai alapján kijelöl egy helyet az \(\displaystyle N+M\) méretű sorozatban. A függvény nem kölcsönösen egyértelmű. Ugyanakkor minél kevesebbszer fordul elő, hogy a függvény két adathoz azonos helyet rendel (hash-ütközés), annál hatékonyabb a tárolás és utána a keresés. Amennyiben az adatok beírásakor ütközés lép fel, úgy a már foglalt hely utáni első üres helyre tesszük az adatot.

Készítsünk programot, amely modellezi és vizsgálja a fent leírt hasítótábla működését. Először vegyünk föl egy \(\displaystyle N+M\) méretű tömböt, amelynek minden elemét jelöljük kezdetben üresnek, tehát egyik sem tartalmaz adatot. Ezután töltsük fel a tömböt az \(\displaystyle N\) számú adattal egy hash-függvényt alkalmazva: ha egy adat számára kijelölt hely szabad, akkor tegyük oda, ha nem szabad, akkor a függvény által kijelölt helyet követő első üres helyre. A tömb utolsó eleme után a tömb első eleme következzen. Az adatok elhelyezése során számoljuk meg, hogy hány esetben (\(\displaystyle T\)) nem sikerült egy elemet a hasítófüggvény által jelölt helyre tenni, illetve összesen hány lépést kellett tenni (\(\displaystyle L\)), hogy az adatoknak üres helyet találjunk. A \(\displaystyle T\) és \(\displaystyle L\) szám jól jellemzi a módszer hatékonyságát, és természetesen függ a hash-függvénytől, valamint \(\displaystyle N\) és \(\displaystyle M\) értékétől.

A program hozzon létre \(\displaystyle N\) számú adatot, amelyek mindegyike egy véletlenszerűen választott szó. A szavakat a word5000.txt szöveges állományból vegyük, minden szót legföljebb egyszer válasszunk ki. A honlapunkról letölthető állományban soronként egy angol szó szerepel. Ezt követően találjunk ki egy hash-függvényt, amely minden szóhoz egy \(\displaystyle 0\) és \(\displaystyle N+M-1\) közötti egész számot rendel, és végezzük el a szavak elhelyezését a kezdetben üres tömbbe úgy, hogy közben kiszámítjuk \(\displaystyle T\) és \(\displaystyle L\) értékét.

A program standard bemenetének első sorában a szavak \(\displaystyle N\) száma (\(\displaystyle 30\leq N\leq 3000\)) és a tömb \(\displaystyle N\)-et meghaladó celláinak \(\displaystyle M\) száma (\(\displaystyle 0\leq M\leq 3000\)) szerepel. A program a standard kimenet egy sorába írja ki \(\displaystyle T\) és \(\displaystyle L\) értékét, valamint a hashtab.txt szöveges állományba a hash-tábla tartalmát: soronként egy szót, üres helyek esetén a ,,—'' karaktersorozatot.

Példa (a várható kimenet a hash-függvénytől és véletlentől függő érték):

Bemenetek	Kimenetek
30 10	18 60
100 0	70 702
1000 500	672 3954
3000 3000	1913 8827
500 2000	159 264

Beküldendő egy tömörített i662.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ó, illetve röviden bemutatja a programban alkalmazott hasítófüggvényt.

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

(10 pont)

megoldás, statisztika