Készítsünk programot, amely felépíti egy megadott aritmetikai kifejezés kifejezésfáját. Az inputkifejezés operandusokat (változónevek vagy számok), műveleti jeleket és zárójeleket tartalmazhat.
A kifejezésfa egy aritmetikai kifejezéshez egyértelműen hozzárendelhető (bináris) fa, amely jól mutatja a kifejezés szerkezetét és a helyes kiértékelésének menetét. A kifejezésfa belső csúcsai műveleti jeleket tartalmaznak, míg levél csúcsai a kifejezés operandusainak feleltethetők meg. Egy műveleti jel gyerekei a művelet operandusai. (Segítség: a kifejezésfa úgy építhető fel a legkönnyebben, ha először a kifejezést lengyelformára alakítjuk.)
Az inputkifejezést a kifejezesfa.in szöveges fájl első és egyetlen sora tartalmazza. A kifejezesfa.out szöveges fájlba négy sort kell kiírni, amelyek a felépített kifejezésfa bejárásait tartalmazzák az alábbi sorrendben: szintfolytonos, preorder, inorder, postorder. Az egyes elemeket a kimenetben egy-egy szóközzel válasszuk el egymástól (a sorok végén is lehet szóköz).
1.1. feladat (8 pont)
Az inputkifejezés a +, -, *, /, ^, = műveleteket tartalmazhatja a szokásos precedenciákkal és zárójeleződési (asszociativitási) szabályokkal. Megengedett a többszörös értékadás is (pl. a=b=0). Egy operandus egy egyetlen betűből álló változónév vagy egy egyetlen számjegyből álló természetes szám lehet.
Minta: kifejezesfa1.in | kifejezesfa1.out
1.2. feladat (+ 2 pont)
Az előző feladat általánosabb változata. Egy változónév betűkből, számjegyekből és _ (aláhúzás) jelekből álló karaktersorozat lehet, de számjeggyel nem kezdődhet, egy konstans tetszőleges természetes szám lehet, továbbá a kifejezés tartalmazhat szóközöket is.
Minta: kifejezesfa2.in | kifejezesfa2.out
Készítsünk programot, amely egy megadott labirintus két pontja között megkeresi a legrövidebb utat. Egy labirintus N×M mezőből áll (N sor és M oszlop), amelyek között vannak falmezők, a többin pedig szabadon lehet mozogni. Egy szabad mezőről négy irányba lehet lépni: balra, jobbra, fel, le, amennyiben a megfelelő szomszédos mező szintén szabad, és nem lépünk ki a labirintus szélén.
A feladatot az alábbi három változatban lehet megoldani, de külön kell programot küldeni mindegyikhez.
2.1. feladat (6 pont)
A program bemenete a labirintus.in szöveges fájlban található (illetve paraméterként megadható a fájlnév). A bemeneti fájl első sora két egész számot tartalmaz egy szóközzel elválasztva: a labirintus 1<=N<=1000 és 1<=M<=1000 méreteit. A második sor négy egész számot tartalmaz egy-egy szóközzel elválasztva, amelyek a kiindulási mező és a célmező pozícióját adják meg. Egy pozíció egy 1<=i<=N sorindexből és egy 1<=j<=M oszlopindexből áll. A fájl következő N sora a labirintust írja le. Mindegyik sor M karaktert tartalmaz, '.' jelöli a szabad mezőket és '#' a falakat.
A programnak az eredményt a labirintus.out szöveges fájlba kell kiírnia. Ha a kezdőpontból a célmező nem érhető el (vagy valamelyik mező fal), akkor az eredmény egyetlen sorból álljon: "Nem erheto el". Ellenkező esetben a fájl első sora egy egész számot tartalmazzon: a legrövidebb út hosszát (a lépések számát). A következő N sor pedig adja meg a labirintust, megjelölve benne a megtalált legrövidebb utat. Mindegyik sor M karakterből álljon az alábbiak szerint: '#' - falmező, 'o' (kis 'o' betű) - az út egy mezője, '.' - az út során nem használt szabad mező.
Minta: labirintus1.in | labirintus1.out
2.2. feladat (+ 4 pont)
A 2.1. feladathoz képest annyi változik, hogy lehetőségünk van a labirintusban található falak felrobbantására is. Az inputfájl egy sorral többet tartalmaz: a labirintus méretei után egy új sorban található egy 1<=C<=1000 egész szám, amely egy szomszédos falmező felrobbantásának és a mezőre lépésnek teljes költségét (idejét) adja meg. A kimeneti fájl formátuma pedig csak annyiban változik, hogy a felrobbantott falakat '@' jellel kell jelöli. Amennyiben a kezdőpont vagy a célmező fal, akkor az eredmény itt is a "Nem erheto el" sor legyen.
Minta A: labirintus2a.in | labirintus2a.out
Minta B: labirintus2b.in | labirintus2b.out
2.3. feladat* (+ 5 pont)
A 2.2. feladathoz képest annyi változik, hogy a bombák száma (vagyis az egy út során felrobbantható falmezők száma) korlátozva van. Az inputfájl második sorában a robbantás 1<=C<=1000 költsége után még szerepel egy 1<=K<=100 egész szám, amely megadja az egy út során felhasználható bombák számát. A kimeneti fájl formátuma nem változik.
Minta A: labirintus3a.in | labirintus3a.out
Minta B: labirintus3b.in | labirintus3b.out
Adott egy tömegközlekedési hálózat, pl. metróvonalak hálózata, amelyben szeretnénk egy megadott megállóból egy másikba utazni a lehető legkevesebb átszállással, valamint azon belül a lehető leggyorsabban.
A program bemenete két fájlból áll. A metro-vonalak.in szöveges fájl a közlekedési hálózatot írja le a következő formában: az első sor a metóvonalak 1<=K<=100 számát és a megállók 1<=N<=10000 számát adja meg, az utána következő sorok mindegyike pedig egy-egy szakaszt határoz meg. Egy szakaszt leíró sor a kezdő- és célállomás 1<=a, b<=N azonosítóit, a metróvonal 1<=v<=K azonosítóját, valamint a szakasz 1<=c<=100 költségét (utazási idő) tartalmazza ebben a sorrendben, egy-egy szóközzel elválasztva. Egy szakaszon mindkét irányban lehet közlekedni (ugyanazzal a költséggel). Átszállásról akkor beszélünk, ha egy utazás két egymást követő szakasza nem azonos járathoz (metróvonalhoz) tartozik. A metro-kerdesek.in szöveges fájl pedig soronként egy-egy feladatot tartalmaz: a kezdőállomás és a célállomás azonosítóját.
Készítsünk programot, amely a metro-kerdesek.in fájlban megadott megállópárok között megkeresi a legkevesebb átszállással járó és azon belül legrövidebb utat. Az eredményeket írja ki a metro-kerdesek.out szöveges fájlba a következő formában. Minden válasz két sorból áll: az első tartalmazza az átszállások számát és a szakaszok összköltségét egy szóközzel elválasztva; a második pedig adja meg az érintett megállók azonosítóját az utazásnak megfelelő sorrendben.
Minta: metro-vonalak.in | metro-kerdesek.in | metro-kerdesek.out
Itt van egy kép is a mintaként megadott közlekedési hálózatról, amellyel az eredmények könyebben ellenőrizhetők: metro-vonalak.png.
Megjegyzés: Az input a moszkvai metróhálózat alapján készült.
4.1. feladat (8 pont)
Adott egy irányítatlan, élsúlyozott, összefüggő, de nem feltétlenül egyszerű gráf. Keressük meg egy minimális költségű feszítőfáját.
A feszitofa.in szöveges fájl első sora tartalmazza a csúcsok 1<=N<=10000 és az élek 1<=M<=1000000 számát, az utána következő M sor pedig egy-egy élt ír le három egész számmal: az él két végpontja (1<=u, v<=N) és költsége (1<=c<=1000).
A feszitofa.out szöveges fájl első sorába a megtalált feszítőfa összköltségét kell írni. A további N-1 sorba pedig a feszítőfa éleit kell megadni ugyanolyan formában, ahogyan az inputban szerepeltek, de a két végpont azonosítója közül mindig a kisebb (nem nagyobb) legyen az első, továbbá az élek lexikografikusan legyenek rendezve!
Minta: feszitofa1.in | feszitofa1.out
4.1. feladat (+ 2 pont)
Az előző feladathoz képest csak annyi változik, hogy a gráf nem feltétlenül összefüggő. Ha nem összefüggő, akkor egy minimális költségű feszítőerdőjét keressük meg, vagyis minden komponensében keressünk egy-egy minimális költségű feszítőfát.
A kimeneti fájl első sora a feszítőerdő összköltségét tartalmazza, a további N-K sor pedig a feszitőerdő éleit az előző pontban megadott szabályok szerint (ahol K a gráf komponenseinek száma).
Ez a feladat nyilván az előző általánosítása, így aki ezt is megoldja, annak elég az általánosabb programot beküldenie.
Minta: feszitofa2.in | feszitofa2.out
Adott egy irányított gráf, határozzuk meg az erősen összefüggő komponenseit.
A komponensek.in szöveges fájl első sora tartalmazza a csúcsok 1<=N<=10000 és az élek 1<=M<=1000000 számát, az utána következő M sor pedig egy-egy él kezdő- és végpontját adja meg két egész számmal (1<=u, v<=N).
A komponensek.out szöveges fájl első sorába a gráf erősen összefüggő komponenseinek K számát kell kiírni, a következő K sorban pedig az egyes komponenseket kell megadni a csúcsaik felsorolásával. A komponensek csúcsait növekvő sorrendben írjuk ki, de a komponensek sorrendje tetszőleges.
Minta: komponensek.in | komponensek.out
A hash-elés témaköréből azt a speciális feladatot vizsgáljuk, amikor pontosan ismert a kulcshalmaz, amelyhez hash-függvényt keresünk. Ez a probléma olyan alkalmazásokban merülhet fel, amikor egy meglehetősen statikus kulcshalmazzal szeretnénk sokat és hatékonyan dolgozni. A legtöbb gyakorlati esetben azonban csak hozzávetőleges információnk van a kulcsok várható eloszlásáról.
Adott személynevek egy listája a input.txt fájlban. Ezen személyek adatait szeretnénk tárolni egy hash-táblában (láncolással). Tekintsük a neveket kulcsoknak (amelyek többnyire nem alkalmasak az egyedi azonosításra, de jelen esetben igen, mert az inputban nincsenek ismétlődő nevek).
A feladat az, hogy erre a kulcshalmazra nézve keressünk egy minél jobb hash-függvényt. Két szempont szerint kell optimalizálni: átlagos és maximális keresési idő szerint. Vagyis azt szeretnénk, hogy ha az adott hash-függvényt használva felépítenénk a hash-táblát, akkor abban a listák hossza minél egyenletesebb legyen, pontosabban az egyes elemek keresésének átlagos és maximális ideje minimális legyen.
Az input.txt fájl 16077 nevet tartalmaz, ezeket a kulcsokat kell leképezni egy 1613 méretű tömb indexeire. A hash.cpp fájl egy C++ program, amelyben a különböző hash-függvényeket kipróbálhatjuk és összehasonlíthatjuk. A fájl tartalmaz egy triviális hash-függvényt, amelyet le kell cserélni. Olyan implementációt keresünk, amelyre a program által kiszámolt átlagos és maximális keresési idő minél kisebb, és a függvény hatékonyan számítható, vagyis a fájlban található triviális változatnál nem lehet lényegesen lassabb, és a tárigénye sem lehet lényegesen nagyobb.
A maximális keresési idő (maximális listahossz) elméleti optimuma 10, az átlagos keresési idő elméleti optimuma pedig 5.485, a cél ezt minél jobban megközelíteni. Olyan hash-függvényeket lehet beküldeni, amelyekre a maximális keresési idő legfeljebb 22 és/vagy az átlagos idő legfeljebb 6,00. Mindenki több függvényt is küldhet.
Megjegyzés: A program csak a hash-táblában tárolandó listákon való lineáris keresések idejét (pontosabban lépésszámát) számolja. Ehhez azonban még minden esetben hozzáadódik a hash-függvény kiszámításának ideje, éppen ezért alapvető kritérium, hogy ez is kicsi legyen.
Értékelés: Ez a feladat tulajdonképpen egy verseny. A pontszámokat a beküldött hash-függvények statisztikai eredményei alapján állapítom meg, a legjobb megvalósításokkal 5-6 pontot lehet szerezni.
