A KöMaL 2023. februári informatika feladatai

I-jelű feladatok A beküldési határidő 2023. március 16-án LEJÁRT.

I. 583. Egy tesztpályán egy robot mozgásának útvonalát vizsgáljuk. A robot mozgását az E, J, B betűk sorozatával vezéreljük. Az E hatására 1 egységet előre lép az aktuális irányba. A J és a B hatására jobbra, illetve balra fordul 90 fokot. A pályán a robot helyzetét derékszögű koordináta-rendszerben adjuk meg. A robot a \(\displaystyle (0,0)\) pontból indul, és kezdetben az \(\displaystyle y\) tengely pozitív irányába néz. A robot a mozgás során nem lép ki a \(\displaystyle (-100,-100)\) és \(\displaystyle (100,100)\) szemközti csúcsokkal jellemzett rácsnégyzetből.

Készítsünk programot, amely megadja, hogy a robot milyen koordinátájú pontra jutott és milyen hosszú nyomvonalat hagyott a tesztpályán.

A program parancssori argumentuma legyen egy adatállomány neve. A fájl egyetlen sort tartalmaz, egy legfeljebb 1000 karakterből álló utasítássorozatot \(\displaystyle E\), \(\displaystyle J\) és \(\displaystyle B\) betűkből.

A kimenet első sorában jelenítsük meg, hogy a robot a mozgás végén milyen koordinátájú pontra jutott, és a kimenet második sorában adjuk meg a robot nyomvonalának hosszát.

Például:

Beküldendő egy tömörített i583.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. 584. (É). A 60. Nemzetközi Matematikai Diákolimpia 5. feladatában szerepel a következő: ,,Bath Bankja érméket bocsát ki, melyeknek egyik oldalán \(\displaystyle \mathrm{H}\), másik oldalán \(\displaystyle \mathrm{T}\) betű látható. Harrynek \(\displaystyle n\) ilyen érméje van, amelyek előtte balról jobbra, egy sorban vannak elrendezve. Harry ismételten végrehajtja a következő műveletet: ha pontosan \(\displaystyle k>0\) olyan érme van, amin \(\displaystyle \mathrm{H}\) van felül, akkor megfordítja a balról \(\displaystyle k\)-adik érmét; máskülönben minden érmén \(\displaystyle \mathrm{T}\) van felül, és ekkor Harry megáll. Például \(\displaystyle n=3\) esetén a \(\displaystyle \mathrm{THT}\) sorozatból indulva \(\displaystyle \mathrm{THT} \to \mathrm{HHT} \to \mathrm{HTT} \to \mathrm{TTT}\) a lépések sorozata, ami három lépés után megáll.''

Modellezzük a feladatban leírt \(\displaystyle n\) (\(\displaystyle n\le 30\)) hosszú sorozat viselkedését legfeljebb 100 lépésen keresztül táblázatkezelő segítségével!

1. Hozzunk létre egy táblázatkezelő munkafüzetet és mentsük bathbankja néven a program alapértelmezett formátumában.

2. Helyezzük el egy munkalapon a ,,Bath bankja'' szöveget az A1-es cellába, valamint az ,,n='' szöveget az A3-as cellába.

3. Hozzunk létre a D3-as cellában és a sorban tőle jobbra egy ,,T'' és ,,H'' betűkből álló 30-tagú sorozatot véletlenszám felhasználásával úgy, hogy a két betűt egyenlő eséllyel kapjuk minden cellában.

4. Írjunk be egy pozitív egész számot a B3-as cellába, amely megadja a vizsgált sorozat hosszát. A 3. sorban generált sorozatból, illetve a később létrehozott sorozatokból csak az első \(\displaystyle n\) darab betűvel foglalkozunk a szimulációban.

5. Adjuk meg képlettel, hogy a generált számokból az első \(\displaystyle n\) darab az 5. sor megfelelő celláiban is megjelenjen, míg a sor további cellái üresen jelenjenek meg.

6. Adjunk meg a B6:B105 tartomány celláiban olyan képletet, amely megadja az adott cella feletti sorban a D oszlopban és attól jobbra lévő betűsorozatban a ,,H'' betűk számát.

7. Adjunk meg a D6:M105 tartomány celláiban olyan képletet, amely a feladat leírásának megfelelően a sorozat \(\displaystyle k\)-adik betűjét kicseréli, míg a többi betűt átveszi a felette lévő sorozatból, ahol \(\displaystyle k\) az előző sorban lévő ,,H'' betűk száma.

8. Állítsunk be a munkalap minden cellájára a mintához hasonló, a tartalom megjelenítéséhez megfelelő oszlopszélességet és formázzuk a munkalapot a mintának megfelelően.

Beküldendő egy tömörített i584.zip állományban a táblázatkezelő munkafüzet, illetve egy rövid dokumentáció, amelyben szerepel a megoldáskor alkalmazott táblázatkezelő neve, verziószáma.

(10 pont)

megoldás, statisztika

I. 585. Aladdin egy szelencében \(\displaystyle N\) darab pénzérmét talált, melyek közül \(\displaystyle 0< k< N\) hamis, a többi valódi. Azt, hogy melyik valódi és melyik hamis, csak Abu, a kismajom tudja megmondani. Aladdin véletlenszerűen kivesz három érmét a szelencéből, az egyiket Abunak adja, cserébe Abu megmondja a másik kettőről, van-e közte hamis. Abu valódi érméért igazat mond, és hazudik, ha hamis érmét kap. Ezután Aladdin megtartja a két érmét, ha Abu szerint nincs közte hamis, és visszateszi a szelencébe, ha Abu szerint van. Ezt addig ismétlik, amíg a szelencében már kevesebb, mint három érme van. Ekkor Aladdin elveszi a maradék érméket.

Készítsünk programot, amely modellezi a fenti folyamatot, és megadja, hogy adott \(\displaystyle k\) és \(\displaystyle 3\le N\le 30\) esetén hány valódi érmére számíthat Aladdin és Abu. A program a standard bemenet első sorából olvassa be \(\displaystyle N\) és \(\displaystyle k\) értékét, majd 1000 véletlenszerű pénzérmesorozattal játssza végig Aladdin és Abu fenti lépéseit. A program a standard kimenet egyetlen sorába két értéket írjon: átlagosan hány valódi érmére számíthat Aladdin és Abu, ha \(\displaystyle N\) érméből \(\displaystyle k\) hamis.

Minta:

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

(A 2023. januári K. 749. feladat alapján)

(10 pont)

megoldás, statisztika

I/S-jelű feladatok A beküldési határidő 2023. március 16-án LEJÁRT.

I/S. 69. Adott egy \(\displaystyle N\) elemű \(\displaystyle T\) tömb, melynek \(\displaystyle i\)-edik elemét \(\displaystyle T[i]\)-vel jelöljük (1-től indexelve). Egy \(\displaystyle (i,j)\) számpárt inverziónak nevezünk, ha \(\displaystyle 1 \le i < j \le N\) és \(\displaystyle T[i] > T[j]\). Szeretnénk a tömbben előforduló inverziók számát csökkenteni, és ehhez pontosan egy elemét törölhetjük a tömbnek. Adjuk meg, hogy minimum mennyi az inverziók száma a \(\displaystyle T\) tömbben, miután annak egy tetszőleges elemét töröltük.

A bemenet első sorában az \(\displaystyle N\) szám található, a tömb hossza. A második sorban \(\displaystyle N\) szám található szóközzel elválasztva, a tömb elemei. A kimenet egyetlen sorában egy szám szerepeljen: a törléssel kapható legkisebb inverziószám.

Minták:

Magyarázat (1. példa): ha töröljük a tömb 5. elemét, akkor az új tömb: \(\displaystyle [4, 4, 2, 5, 5]\), melyben az inverziók száma 2, és ez a legkisebb elérhető inverziószám.

Korlátok: \(\displaystyle 2 \le N \le 10^{5}\); \(\displaystyle 1 \le T[i] \le 10^{5}\) egész számok. Időkorlát: 0,4 mp.

Értékelés: a pontok 30%-a kapható, ha a program helyes kimenetet ad az \(\displaystyle {N \le 100}\) esetekben. További 30% kapható, ha a program helyes kimenetet ad az \(\displaystyle {N \le 1000}\) esetekben.

Beküldendő egy is69.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ó. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

statisztika

S-jelű feladatok A beküldési határidő 2023. március 16-án LEJÁRT.

S. 168. Egy leegyszerűsített felvételi eljárásban minden felvételiző legfeljebb 6 egyetemi szakra adhatja le a jelentkezését. Mindenki a saját listáján szereplő sorrend szerint szeretne bekerülni az adott képzésekre. Ha az első helyről elutasítják, akkor a második helyre kerül, ha a másodiktól is elutasítják, akkor a harmadikra stb. Ha egyik szakra sem veszik fel, akkor nem mehet egyetemre. Mivel a képzések pontszámítási rendszere eltérhet, ezért a felvételiző pontját minden szakra külön meg kell adni.

A felvételi a ponthatárok meghúzásával történik. Minden egyetem minden szakra megad egy ponthatárt. Ha egy felvételiző a ponthatárnál nagyobb vagy egyenlő pontszámot ért el, és a listájában előbb lévő szakokra nem vették fel, akkor az adott szakra veszik fel. Ha valakit több helyre is felvennének a pontjai alapján, akkor is csak a listájában legelöl lévő szakra iratkozhat be.

A ponthatárokat úgy kell meghúzni, hogy azok mindenhol a lehető legalacsonyabbak legyenek, de az egyetem ne lépje át az egyes szakokra kiszabott kvótát, azaz ne vegyen fel adott számú hallgatónál többet. Fontos szabály, hogy az azonos pontszámú hallgatókat csak együtt lehet felvenni, illetve elutasítani.

Adott az összes felvételiző preferencialistája a kiszámított felvételi pontokkal együtt és a szakok kvótái. Adjuk meg, melyik a legalacsonyabb ponthatár, amivel még valamelyik szakra be lehet kerülni, valamint adjuk meg, hogy hány felvételizőt nem vettek fel sehova.

A bemenet első sorában a felvételizők száma, \(\displaystyle F\) és az egyetemi szakok \(\displaystyle E\) száma szerepel. A következő \(\displaystyle F\) sor mindegyikében egy-egy felvételiző preferenciasorrendje, azaz legfeljebb 6 számpár szerepel. Minden számpár első tagja a szak sorszáma, a második tagja pedig a felvételiző pontszáma arra a szakra. A következő sorban a szakok \(\displaystyle E\) száma szerepel. Az alatta lévő sorban \(\displaystyle E\) szám szerepel. Az \(\displaystyle i\)-edik szám az \(\displaystyle i\)-edik szak kvótája, amit a felvettek száma nem léphet át.

A kimenet első sorába a legalacsonyabb ponthatárt kell írni. A kimenet második sorába azon felvételizők száma kerüljön, akik nem jutottak be sehova.

Példa:

Magyarázat: az első szakra az első két felvételiző jut be. A harmadik lemarad az első szakról, így kiejti a negyedik felvételizőt a második szakról.

Korlátok: \(\displaystyle 1\le F \le 10\,000\), \(\displaystyle 1\le E \le 1000\). Az egyetemek 1-től \(\displaystyle E\)-ig sorszámozottak. A pontszám 0 és 500 közötti egész szám. Időkorlát: 1 mp.

Értékelés: a pontok 40%-a kapható, ha a program helyes kimenetet ad az \(\displaystyle F, E\le 100\) bemenetekre.

Beküldendő egy s168.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ó. A dokumentáció tartalmazza a megoldás elméleti hátterét, az esetleg felhasznált forrásokat. Ne tartalmazzon kódrészleteket, azok magyarázata kódkommentek formájában a forrásprogramban szerepeljen.

(10 pont)

statisztika