Az elődöntő: 2009. március 26-án 18-21 óráig tart. • • • •
• • • • •
A feladatok itt érhetőek el. Csak az ide feltöltött megoldások számítanak. Tetszőleges programozási nyelv használható. Minden feladatmegoldáshoz (ahol programkód az eredmény) mellékelni kell: o A forráskódot (illetve a fordításához szükséges minden állományt): 24_csapatszam_feladatszam_source.zip vagy 24_csapatszam_feladatszam_source.tgz-ben o A futtatható programot 24_csapatszam_feladatszam_bin.zip vagy 24_csapatszam_feladatszam_bin.tgz-ben o A .._bin tartalmazzon egy platform.txt fájlt, mely a következőkből áll (csak a platformon értelmes mezőket kell kitölteni): operációs rendszer neve és verziója pl.: Ubuntu Linux 6.10 vagy Windows XP processzor típusa, amire a kódot fordították pl.: i586 a fordítóprogram vagy interpreter nevét és verzióját pl.: gcc 4.0 vagy PHP5 a felhasznált dinamikus könyvtárakat pl.: xmath, mfc.dll esetleges speciális fordítási kapcsolókat pl.: -lm A feladatok tetszőleges sorrendben megoldhatóak és feltölthetőek. Csak a működő programokat értékeljük. A feladatok különböző jellegűek és nehézségűek, különböző pontszámot érnek. Azonos megoldásokat beadó csapatokat egységesen kizárjuk a versenyből. Azonos ponteredmény esetén az a csapat végez előbbre, aki a legutoljára beadott megoldását korábban adta be.
Technikai problémákkal az elődöntő időtartama alatt a 70/592-3020-as mobilszámon vagy a következő ICQ számon jelentkezzenek: 270339944 Jó munkát!
1. Feladat (1 pont): Szorzat Gondoltam két prímszámra. E két számot összeszoroztam, eredményként az alábbi számot kaptam: 310006313813743287982155119549168581 A Moodle rendszerbe feltöltendő egy txt fájlban a nagyobb szám legnagyobb és a legkisebb helyi értékű számjegyeinek szorzata (programot vagy egyéb fájlokat nem kell mellékelni a feltöltéshez)!
2. Feladat: Körjárat (1 pont) Adott egy város úthálózata. A városban minden út egyirányú! A helyi közlekedési vállalatnak segítsünk eldönteni, hogy tud-e körjáratot üzemeltetni a városban! Ha igen, akkor adjunk meg egy olyan útvonalat (elegendő egyet), amin a busz majd körjáratként közlekedhet. Fontos! Nem kell, hogy a körjárat minden utat/kereszteződést érintsen, a lényeg, hogy a járat oda jusson vissza ahonnét elindult! A program bemenetként (in.txt) egy szomszédossági mátrixot kapjon, mely a város úthálózatának irányított gráfját reprezentálja (feltesszük, hogy a gráf nem tartalmaz hurokélt). A fájl első sora a gráf csúcsainak számát mutassa, az ezt követő sorok a szomszédossági mátrixot tárolják. Példa. Egy szomszédossági mátrix és a neki megfeleltethető úthálózat: 0 1 1 0
0 0 1 0 1 1 0 0 1 0 1 0
A program kimeneti (out.txt) állományának első sora az Igen/Nem szavak egyikét tartalmazza attól függően, hogy létezik-e körjárat vagy nem. Igen válasz esetén a fájl második sora tartalmazza a körjárat gráf-csúcsainak egy felsorolását! Futási példa: korjarat in.txt out.txt in.txt: 4 0001 1011 1001 0010 out.txt: Igen 1431
3. Feladat: Gyümölcsszedő (3 pont) Készítsen olyan – lehetőleg grafikus – játék-alkalmazást, mely a képernyőn a bemeneti paraméterben kapott darabszámú (legalább 2, legfeljebb 6) gyümölcsfát jelenít meg. Ezen gyümölcsfákról a játékot elindítva „potyognak” a földre a gyümölcsök. A cél az, hogy adott idő alatt (pl. 1 perc alatt) a játékos minél több gyümölcsöt tudjon elkapni esés közben egy kosár segítségével mielőtt az még a földre esne. A kosár vízszintes irányban legyen mozgatható a képernyő alsó részén a kurzormozgató billentyűkkel! A játékidő leteltével jelenítsük meg az eredményt a képernyőn, azaz mutassuk meg, hogy a játékos hány darab gyümölcsöt tudott begyűjteni! Hívási példa: gyumolcsszedo 4
4. Feladat: Részsztring keresés (3 pont) Írjon programot, mely paraméterként egy txt fájlt kap. Ezen fájl (in.txt) első és második sora is egy-egy sztringet tartalmazzon. Feladatunk megtalálni a két sztring egy olyan közös részsztringjét (kis és nagybetűk között ne tegyünk különbséget), mely maximális hosszúságú! Eredményként egy out.txt fájlban jelenítsük meg • •
a leghosszabb közös részsztringet (elegendő egyet megadni, ha több ilyen is van); és annak hosszát!
Természetesen az is előfordulhat, hogy nem létezik közös részsztring! A részsztring fogalmat a következőképpen értelmezzük: Ha az s sztring n karaktert tartalmaz, azaz s=a1a2a3…an, ahol ai karakterek (i=1, …, n), akkor ennek egy részsztringje az üressztring, valamint minden aiai+1ai+2…aj-1aj karatersorozat, ahol 1 ≤ i ≤ j ≤ n. Hívási példa: keres in.txt out.txt in.txt: CAABABABG CABABDEF out.txt: ABAB 4
5. feladat: Kódolás (1+2 pont) Üzeneteinket biztonsági szempontok miatt gyakran kódoljuk, majd dekódoljuk. Készítsen programot, mely egy titkos üzenetet dekódol a kódtábla ismeretében. Feltéve például, hogy az alábbi kódtáblával dolgozunk, az 11001100000100011110010 jelsorozat a „linux” szót tárolja. A kódtábla egy részlete, mely segítségünkre van a dekódolásban ez esetben az alábbi volt: Karakter a i m n l o u x
Kód 010 1000 0111 0010 11001 00110 00111 10010
Az elkészítendő program feladata egy kódolt üzenet dekódolása, melyet a képernyőn jelenítsünk meg. A programot két paraméterrel hívhatjuk meg: • az első paraméter tartalmazza a kódtáblát tartalmazó XML fájl nevét (szóval a kódtábla nem rögzített!), • a második paraméter egy in.txt fájl, melynek első sorában magát a kódolt üzenetet tároljuk. A karakter-kód párokat tartalmazó XML fájl felépítése minden esetben az alábbi legyen (tabla.xml):
nev=”a” kod=”010”/> nev=”i” kod=”1000”/> --> nev=”x” kod=”10010”/>
Figyelem! Dekódoláskor előfordulhat, hogy • olyan kódtáblát kapunk bemenetként, mely nem prefixmentes. Ez azt jelenti, hogy egy kód kezdőszelete (prefixe) lehet egy másik kódnak. Például, ha az „e” betűt a 01 kód reprezentálja, az „a” betűt pedig a 01011, akkor a dekódolás már nem feltétlenül lesz egyértelmű! Ilyen esetben minden lehetséges dekódolt szót ki kell írnia a programnak. • a kódtábla nem tartalmazza a bemenetként kapott kódot és a hozzá társítható karaktert az xml fájlban. Ekkor jelezzük, hogy a szöveg nem dekódolható! A feladatért 1 pont kapható, ha csak prefixmentes kódtáblákra működik helyesen, és további 2 pont szerezhető, ha a nem prefixmentes kódtáblával is helyesen dolgozik a program. Hívási példa: dekodol tabla.xml in.txt A dekódolás eredményét a képernyőre írjuk ki!
6. feladat: Különbségek (3 pont) Készítsünk programot, amely 2 kép között megkeresi a különbségeket. A program bemenete 2 képfájl, a kimenete egy kép, amin pirossal be vannak jelölve a különbségek. A különbségeket a képen össze kell számolni, és a kimeneti képre a sorszámot rá kell írni. A különbségek sorrendje és a sorszámok elhelyezése tetszőleges, de be lehessen őket azonosítani. Csak azokat a különbségeket kell jelölni és számolni, ahol az egymás mellett levő eltérő pixelek száma legalább 20 (néhány pixeles eltéréseket figyelmen kívül kell hagyni). A képfájlok formátuma bmp vagy png legyen. Bemeneti képek:
Kimeneti kép:
Futtatási példa: kulonbsegek kep1.bmp kep2.bmp out.bmp Mintakép a Moodle-ban elérhető!
7. feladat: Weboldal keresés (2 pont) Készítsünk olyan programot, ami megadja, hogy a weboldalunk egy adott kulcsszóra az Altavista keresőben hányadik oldalon található. Pl: A böngészőben az Altavista oldalán (http://www.altavista.com/), az „optimization” kulcsszóra rákeresve a keresett www.websiteoptimization.com weboldal a találati lista második oldalán található. Bemenet: Kulcsszó, keresett weboldal url („optimization”, „www.websiteoptimization.com”) Kimenet a képernyőn: Hányadik oldalon található (2. oldal) Megjegyzések: • Az Altavista keresőjében (www.altavista.com) kell az oldalszámot megadni. Alapbeállításban egy találati oldalon 10 weboldal címe van plusz még az esetleges fizetett hirdetések. Így kell érteni az oldalszámot. • Ha a keresett weboldal szponzorált linkként megjelenik pl. az első oldalon, akkor természetesen az első oldal legyen a program kimenete. Nem kell azt megvizsgálni, hogy az „normál” találatként mikor jönne elő.
8. feladat: Csónakázás (4 pont) Egy nyugat-keleti egyenes országutat egy északon eredő, délre haladó kanyargós folyó 7-szer átmetsz. A 7 hidat számozzuk meg az országút mentén nyugatról keletre az 1-7 számokkal. A folyón északról délre utazva írjuk fel milyen sorrendben utazunk el a hidak alatt. Például az alábbi ábrán a 3214765 sorozatnak megfelelő áthaladás látható.
Megjegyzés: a folyó nem keresztezheti önmagát, tehát pl.: az 1324765 sorozat nem elfogadható. Kimenet: A program listázza ki az összes lehetséges sorozatot, majd az utolsó sorban adja meg a megoldások számát. Pl.: 3214765 3214567 … Összesen x db lehetőség
9. feladat: Tili-toli (2 pont) Készítsen Tili-toli játékot! Az alábbi példában a bal oldalon látható képet 4×4 kockára osztotta fel a program. A jobb alsó kockát eltávolítva, a kurzorbillentyűkkel vagy az egérrel a felhasználó számára adott a lehetőség a képkockák tologatására, így a kép összekeverésére (lásd jobb oldali ábra).
A programnak két paramétere legyen: a betöltendő kép neve, valamint a felosztás mértéke. Meghívás után a program jelenítse meg a képet, a jobb alsó kocka kivételével és adjon lehetőséget a képdarabok mozgatására. Hívási példa: tilitoli kep.bmp 4 A fenti hívás a kep.jpg képet 4×4 részre osztja fel. A kép formátuma bmp vagy jpg lehet, elegendő egyiket kezelni.
10. feladat: Zene (3+1pont) A Kocsis család tagjai, mint a művészek általában, nagyon szórakozottak. Letöltenek zenéket mp3 formátumban, elmentik ide-oda, majd később napokig keresgélnek, ha valamit újból meg szeretnének hallgatni. Persze, azt is hamar elfelejtik, mit töltöttek már le. A tárolók méretének gyors növekedése egyre jobban ront a helyzetükön. Olyan alkalmazásra van szükségük, amelyik kigyűjti nekik a kiválasztott mappákból és almappáikból az mp3 kiterjesztésű fájlokat és a róluk elérhető legtöbb információt (pontos elérési út, szerző, cím, méret,…), és megjeleníti olvasható formában. Külön értékelik, ha a kigyűjtött információkat csoportosítani tudják szerző és előadó szerint (+1 pont). Futtatás: zene c:\zene\bruno A bemenetnél megadott mappa: c:\zene\bruno A kimenetnél kapott információk a képernyőn: c:\zene\bruno\3 ------------------------Title: Brothers In Arms Artist: Dire Straits; Composers: Mark Knopfler; … ------------------------… -----------------------Title: … Artist:… Composers: … … ------------------------c:\zene\bruno\lajos\komoly -----------------------Title: … Artist:… Composers: … …
11. Feladat: Füttykód (3 pont) A rigók 4 jegyű pin kódjaikat füttysorozat segítségével jegyzik meg a következőképpen. Átváltják a kódot kettes számrendszerbe, majd ennek megfelelő füttysorozatot hallatnak. A fütty 1-es jelent, a csönd 0-át. Sajnos nem tudtak megállapodni abban, hogy milyen hosszan fütyüljenek egy jelet, de egy adott rigó jelei egyforma hosszúak, és minden kódot fütty-szünfütty záró dallammal fejeznek be. Állapítsa meg a program, mi a fütyülő rigó pin kódja. Például: Az 1451 pin kódhoz tartozó bitsorozat a következő: 10110101011101 Futtatás: futty in.wav Bemenet: Egy füttysorozatot tartalmazó wav fájl (minta fájl a Moodle rendszerből letölthető). Képernyőn a kimenet: A füttysorozathoz tartozó kód.
12. feladat: Verseny (3 pont) Egy országos programozási verseny eredményét a pontosvesszővel határolt forras.csv fájlban tárolják. A feladat tetszőleges adatbázis-kezelőhöz sql script elkészítése. Az sql sript: • hozza létre a forras.csv fájl adataiból a következő táblákat:
• Hozzon létre a tanulo táblában egy új mezőt, amelyik az összpontszámot tartalmazza a következő képlet alapján: osszpontszam=round(ford1/4)+ii1+ii2+ii3+ii4+ii5. • Törölje a HB régióhoz (rvb) tartozó tanulókat. • Listázza ki városonként a legjobb eredményt elért tanulót. Az forras.csv fájl a Moodle rendszerből letölthető. Feltöltendő a Moodle rendszerbe az adatbázis-kezelő pontos leírását tartalmazó fájl, és a feladatot végrehajtó sql script.
