 |
Az S. 65. feladat (2011. október) |
S. 65. Már a korabeli azték birodalom fénykorában is szükségesnek látták az uralkodói üzenetek titkosítását. A neves régész, Kamoo professzor szerint a kódolás alapja Ometeotl, a kettőség istenének két jele: a férfias erőt (<) és a női gyengédséget (>) jelképező két szimbólum volt. Ezekből az istenség parancsára csak az alábbi két szabály betartásával volt szabad jelsorozatokat létrehozni:
-- érvényesülnie kellett az egyensúlynak, tehát azonos számú < és > jel szerepelt minden sorozatban;
-- balról-jobbra olvasva a sorozatot annak tetszőleges jeléig mindig több, vagy azonos számú férfi szimbólum szerepelt, mint női szimbólum, tehát az erőt és aktivitást jelképező szimbólumok mindig megelőzték a gyengédséget és passzivitást jelölő szimbólumokat.
A vázolt módon létrehozhatóak különböző hosszúságú jelsorozatok, melyek sorba rendezhetők a hosszúságuk, illetve a < jelek elhelyezkedése alapján:
(1) A rövidebb jelsorozatok előbb vannak, mint a hosszabbak;
(2) az azonos hosszúságúakon lexikografikus rendezést alkalmazunk (ha tudunk, akkor az első betű alapján döntünk; ha ezek megegyeznek, akkor a második alapján stb.).
Például a legföljebb hat hosszúságú jelsorozatok sorrendje:
<>
<<>>
<><>
<<<>>>
<<><>>
<<>><>
<><<>>
<><><>
Ennek alapján tehát van egy (végtelen hosszú) rendezett R listája a < és > szimbólumokból álló jelsorozatoknak. Ezután a kódolás egyes lépései a következők voltak:
(1) A nyelv betűi (az egyszerűség kedvéért az angol ábécét használjuk) és a szóköz megfelelnek a 27-es számrendszer számjegyeinek (,
,
, ...,
);
(2) az üzenetet b hosszúságú blokkokra bontjuk (ha a szöveg hossza nem osztható b-vel, akkor szóközökkel kipótolják a végét);
(3) az egyes blokkokat kiolvassuk 27-es számrendszerbeli számokként;
(4) az így kapott számoknak megfelelő sorszámú jelsorozatokat kiválasztjuk a fenti R listából és ezeket szóközökkel elválasztva egymás után írjuk.
Készítsünk programot ami képes kódolni, illetve dekódolni az uralkodó üzeneteit.
A bemeneti állomány első sorában a blokkok b hossza szerepel (1
b12). A második sorban egy kódolandó vagy dekódolandó karaktersorozat szerepel. A szóközökön kívül, az előbbiekben csak az angol ábécé kisbetűi, az utóbbiakban pedig csak a < és > karakterek szerepelnek. Feltehetjük, hogy a bemenet nem kezdődik szóközzel.
A kimeneti állomány egyetlen sorába a kódolás vagy dekódolás eredményét írjuk.
Megjegyzés: A példákban a kódolt üzenetekben a szóközök helyett néhol sortörések látszanak.
(10 pont)
A beküldési határidő 2011. november 10-én LEJÁRT.
A feladatot dinamikus programozással lehetett hatékonyan megoldani. Mintamegoldásként Adrián Patrik, és Marussy Kristóf megoldásait közöljük.
A két megoldás hasonló, viszont utóbbiban egy formálisabb, részletesebb leírás található.
Statisztika:
11 dolgozat érkezett. 10 pontot kapott: Adrián Patrik, Havasi 0 Márton, Marussy Kristóf, Nagy Róbert, Strenner Péter, Szabó 262 Lóránt, Szilágyi Dániel. 9 pontot kapott: Szabó 928 Attila. 7 pontot kapott: 1 versenyző. 5 pontot kapott: 1 versenyző. 3 pontot kapott: 1 versenyző.
A KöMaL 2011. októberi informatika feladatai