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 2015. novemberi 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ő 2015. december 10-én LEJÁRT.


I. 385. A Playfair-féle titkosítási eljárást (Forrás: https://hu.wikipedia.org/wiki/Playfair-rejtjel) a fizikai tanulmányainkból ismert Charles Wheatstone találta ki 1854-ben, de azt barátjáról, a módszert népszerűsítő Lord Playfairről nevezték el. Magát az eljárást már az első világháború előtt feltörték, azonban az ausztrálok még a II. világháborúban is használták. (Akkoriban, számítógépek nélkül, a feltöréshez szükséges idő még hosszabb volt, mint amennyi ideig az információ titkosnak számított.)

Az eljárás alapját egy \(\displaystyle 5\times 5\)-ös táblázat alkotja, amely az angol ábécé betűit tartalmazza (az angol ábécé 26 betűs, így ebből egyet, esetünkben a Q-t, el kell hagyni). Természetesen ezt a táblát csak a küldő és fogadó fél ismerheti.

A titkosítandó szöveget (példánkban FINOM IZ) betűpárokra tagoljuk, szükség esetén az utolsót egy megválasztott jellel (a feladatban legyen X) kiegészítjük. Hasonló módon járunk el, ha a betűpár két eleme azonos, például az AA betűpárt AX AX betűpárokká alakítjuk át.

Az eljárás a betűpárokhoz rendel betűpárokat az alábbiak szerint:

\(\displaystyle \bullet\) Ha a két betű a táblázatban egy sorban van, akkor azokat a tőlük eggyel jobbra lévő betű rejtjelezi. Az utolsó oszlopban lévő betűt az adott sor első betűje követi (FI \(\displaystyle \to\) RN).

\(\displaystyle \bullet\) Ha a két betű egy oszlopban van, akkor azokat az alattuk lévő betű rejtjelezi. Az utolsó sorban lévő betűt az adott oszlop első betűje követi (NO \(\displaystyle \to\) VN).

\(\displaystyle \bullet\) Végül, ha a két betű különböző sorban és különböző oszlopban van, akkor tekintsük azt a ,,betűtéglalapot'', amelyben a két betű egy ,,átló'' két végpontja. A betűket ekkor a saját sorukban, a téglalap másik csúcsánál lévő betűkkel helyettesítjük (MI \(\displaystyle \to\) KF).

A program első parancssori argumentuma egy karakter, amely megadja, hogy a felhasználó az adatokat rejtjelezni vagy visszafejteni szeretné-e (R/V), második a Playfair-rejtjelező táblázatot sorfolytonosan tartalmazó fájl neve, a harmadik a rejtjelezendő/visszafejtendő adatokat tartalmazó fájl neve, a negyedik pedig a kimeneti fájl neve legyen.

Feltételezhetjük, hogy a bemeneti adatok csak az angol ábécé fentieknek megfelelő nagybetűit tartalmazzák. A programot úgy készítsük el, hogy a rejtjelezendő/visszafejtendő állomány mérete tetszőleges, akár több GB-os is lehet.

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

Letölthető fájlok (egy lehetséges Playfair-rejtjel, valamint egy lehetséges rejtjelezendő fájl): kod.txt, be.txt.

(10 pont)

megoldás, statisztika


I. 386. Egy kisváros Juhász Gyuláról elnevezett iskolájának weblapján a 2011-es tanév kezdetétől minden nap a névadó egy-egy versét ajánlják a látogatók figyelmébe. A verseket a látogatók lájkolhatják. Az adatbázis három tanév adatait tartalmazza.

Készítsünk új adatbázist jgy néven. A mellékelt két - tabulátorokkal tagolt, UTF-8 kódolású - szöveges állományt ( vers.txt, napverse.txt) importáljuk az adatbázisba a fájlnévvel azonos néven (vers, napverse). Az állomány első sora a mezőneveket tartalmazza. A létrehozás során állítsuk be a megfelelő típusokat és kulcsokat.

Táblák:

A következő feladatok megoldásánál a lekérdezéseket a zárójelben olvasható néven mentsük. Ügyeljünk arra, hogy a megoldásban pontosan a kívánt mezők szerepeljenek.

1. Listázzuk ki az ajánlás dátumának sorrendjében a 2011. szeptemberben ajánlott verseket. A vers címét és az alkotási évet jelenítsük meg. (2szept)

2. Adjuk meg, hogy a többször választott versek közül átlagosan melyik három gyűjtötte a legtöbb lájkot. (3like)

3. Készítsünk jelentést, amely a 2013/2014 telén (december és február között) ajánlott verseket készítési évük szerint csoportosítva ábécérendben listázza ki. (4tel)

4. Határozzuk meg azokat a verseket, amelyeket mind a négy naptári évben választottak. (5negyev)

5. Határozzuk meg azokat a verseket, amelyeket csak 2011-ben választottak. (6csak2011)

6. Határozzuk meg, hogy mely napokon fordult elő, hogy a választott vers ugyanabból az évből származott, mint az előző napi. (7azonosev)

7. Határozzuk meg, hogy Juhász Gyulának az első vagy az utolsó alkotói évtizedében született-e több vers. Az alkotói évtized első évét jelenítsük meg. (8evtized)

Beküldendő egy tömörített állományban (i386.zip) a megoldást tartalmazó adatbázis vagy az SQL lekérdezéseket tartalmazó szövegfájl, valamint egy rövid dokumentáció, amelyből kiderül az alkalmazott adatbázis-kezelő neve és verziószáma.

Letölthető állományok: vers.txt , napverse.txt.

(10 pont)

megoldás, statisztika


I. 387. A római számok arab számokká alakítása volt a témája a 2012. májusi emelt szintű informatika érettségi gyakorlati vizsga táblázatkezelés feladatának. Az ott megadott algoritmust funkcionális programozással is megvalósíthatjuk.

Alakítsuk át a római számokat arab számokká a megadott algoritmus alapján Logo nyelvű programmal. A római szám íráshelyességének vizsgálata most nem szükséges. Csak 1-től 4000-ig terjedő, nagybetűs római számokkal foglalkozunk, amelyek legfeljebb 20 karakterrel leírhatók.

Az átalakítás algoritmusa:

Az adott számjegy előjele akkor negatív, ha az utána következő számjegy nála nagyobb. Az utolsó számjegyérték mindenképpen pozitív.

Készítsük el az algoritmus egyes lépéseit megvalósító Logo szavakat, majd ezek segítségével az átváltást végrehajtó római_tízes szót.

Példa a parancsra Eredmény
római_tízes "MCCXCIV 1294

A megoldás során csak a programozási nyelv automata és funkcionális részét használjuk. Ne alkalmazzunk változókat, csak paraméterezést.

Beküldendő a program projektállománya, forráskódja (i387.imp).

(10 pont)

megoldás, statisztika


I/S-jelű feladatok

A beküldési határidő 2015. december 10-én LEJÁRT.


I/S. 3. Egy boltban \(\displaystyle 1\le N\le 1000\) árut lehet vásárolni. Ehhez \(\displaystyle 1\le P \le 1\;000\;000\;000\) pénz áll rendelkezésünkre. Minden terméknek van egy \(\displaystyle A_i\) ára, és egy \(\displaystyle H_i\) házhozszállítási költsége, így a teljes költség az \(\displaystyle i\). árura \(\displaystyle A_i+H_i\) (nemnegatív egészek, \(\displaystyle A_i\) a feladat megkönnyítése miatt páros). Van egy kuponunk, amivel egy választott termék árát megfelezhetjük, azaz \(\displaystyle A_i/2+H_i\)-ért kaphatjuk meg, ha az \(\displaystyle i\). termékre használjuk fel. Adjuk meg, legfeljebb hány terméket tudunk megvásárolni a boltban, ha egyetlen kupont használhatunk fel.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle P\)-t, majd a következő \(\displaystyle N\) sorból az \(\displaystyle A_i\), \(\displaystyle H_i\) szóközzel elválasztott egészeket, és írja a standard output első és egyetlen sorába maximálisan megvásárolható termékek számát.

Magyarázat: az első 4 terméket meg tudjuk venni, ha a 3.-ra használjuk fel a kupont.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített is3.zip állományban a program forráskódja az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2015. december 10-én LEJÁRT.


S. 102. Egy robot a következő utasítások szerint mozog: először a 0 pozícióból indul, majd a 15 R utasításra 15 lépést jobbra lép, és a 20 L utasításra 20 lépést balra. A robotnak \(\displaystyle N\) utasítást adnak, \(\displaystyle 1\le N\le 300\;000\). Az utasítások lépésszámai pozitív egészek, a robot legfeljebb \(\displaystyle 1\;000\;000\;000\) távolságra mehet el a kezdőpozíciótól. Adott még egy \(\displaystyle K\) szám. Az a kérdés, hogy hány pozíción volt, vagy haladt át a robot legalább \(\displaystyle K\)-szor.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle K\)-t, majd a következő \(\displaystyle N\) sorból az \(\displaystyle a_i\), \(\displaystyle c_i\) szóközzel elválasztott számot és karaktert, melyek a robot mozgását írják le. A program írja a standard output első és egyetlen sorába a megfelelő pozíciók számát.

Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül.

Beküldendő egy tömörített s102.zip állományban a program forráskódja az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja, amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

megoldás, statisztika


Figyelem!

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