Házi feladat

Általános leírás

Törekedj arra, hogy szép, áttekinthető kódot írj! Úgy oldd meg a feladatokat, hogy függvényeket használsz a megoldáshoz! A felhasznált függvényekben ne történjen konzolra való kiírás!

Mindegyik feladatban nagyon fontos, hogy bár egyetlen inputfájlt kapsz, úgy írd meg a programod, hogy bármilyen, a feladatkiírásnak megfelelő inputfájllal működjön!

3.100-K Jutalomkönyvek

Az iskola egy logikai feladatmegoldó verseny három díjazottjának szeretne jutalomkönyvet venni. Mindhárom tanuló egy-egy könyvet kap, és a szervezők azt szeretnék, hogy három különböző című kötetet válasszanak. A könyvlistán kizárólag Raymond M. Smullyan művei szerepelnek.

A jutalmakra rendelkezésre álló összeget teljes egészében könyvekre kell költeni. Keresd meg, választható-e három különböző könyv úgy, hogy az áruk összege pontosan a megadott keretösszeg legyen! A keretet túllépni nem lehet, és megmaradó pénz sem lehet. Kedvezménnyel, szállítási költséggel vagy más felárral nem számolunk.

Bemeneti fájl

Az input.txt UTF-8 kódolású fájl első sora mezőneveket tartalmaz. Minden további sor egy könyv címét és forintban megadott árát tartalmazza, pontosvesszővel elválasztva, ebben a sorrendben:

Cim;Ar

A könyvcímek egyediek. A címek szóközt és írásjeleket is tartalmazhatnak, de pontosvesszőt vagy sortörést nem; a mezők nincsenek idézőjelezve. Az árak pozitív egész számok. Különböző könyvek ára megegyezhet, és ezeket továbbra is külön könyvként kell kezelni. A fájl legalább három könyvet tartalmaz, a sorok sorrendje tetszőleges.

A mellékelt fájl harminc könyvet tartalmaz, de a programod más elemszámú, a leírásnak megfelelő fájlokkal is működjön! A címek valódi könyvcímek, az árak viszont a feladathoz kitalált tesztadatok, nem aktuális bolti árak.

Feladatok

Minden részfeladat előtt írd ki a sorszámát!

1. Olvasd be és tárold a könyvek címét és árát! Írd ki, hány könyv közül választhatnak a szervezők!
2. Kérd be a felhasználótól a keretösszeget forintban, pozitív egész számként! Hibás adat esetén kérd be újra!
3. Rendezd a könyveket ár szerint növekvő sorrendbe! A címet és az árat együtt mozgasd; azonos ár esetén a könyvek sorrendje tetszőleges.
4. Készíts függvényt, amely a rendezett könyvlista és a keretösszeg alapján visszaad három megfelelő könyvet, vagy jelzi, ha nincs megoldás! Ugyanazt a könyvet nem választhatod ki többször. Azonos árú, de különböző című könyveket viszont választhatsz együtt. Több megfelelő hármas esetén bármelyiket megadhatod; elég egyetlen megoldást keresni.
5. Ha van megoldás, írd ki a három könyv címét és árát az árak növekvő sorrendjében, majd az összárukat! Ha nincs, írd ki: Nincs három különböző könyv, amelynek összára pontosan a megadott keret.

Algoritmikus megkötés

A kereséshez használd ki az árak szerinti rendezettséget! Rögzíts egy könyvet, majd a mögötte álló listarészben két mutatóval keresd a másik kettőt! Az egyik mutató e rész elejéről, a másik a végéről induljon. Az aktuális összeg alapján döntsd el, melyik mutatót kell léptetni! Egy rögzített első könyvnél a mutatók csak egymás felé haladhatnak, és nem keresztezhetik egymást.

A rendezés utáni keresés futási ideje legfeljebb O(n²) legyen, ahol n a könyvek száma. Egy rögzített első könyvhöz a másik kettőt legfeljebb lineáris időben keresd meg! Ne próbáld végig az összes könyvhármast három egymásba ágyazott ciklussal, és ne helyettesítsd a kétmutatós keresést minden könyvpárhoz indított külön bináris kereséssel! A függvény visszatérési értékkel jelezze az eredményt; ne a keresőfüggvény írjon a képernyőre!

Példa a mellékelt bemenettel

A könyvlista egyik részlete:

Cim;Ar
Sherlock Holmes sakkrejtélyei;3200
Alice Rejtvényországban;2900
Seherezádé rejtélye;3500
Mi a címe ennek a könyvnek?;3200

A teljes fájl további könyveket is tartalmaz. Ha a felhasználó 10000 forintos keretet ad meg, egy megfelelő eredmény:

Alice Rejtvényországban;2900
Sherlock Holmes sakkrejtélyei;3200
Emlékek, történetek, paradoxonok;3900
Összesen: 10000 Ft

Másik helyes választás ugyanennél a keretnél:

Sherlock Holmes sakkrejtélyei;3200
Mi a címe ennek a könyvnek?;3200
A hölgy vagy a tigris?;3600
Összesen: 10000 Ft

Ez is érvényes: a két 3200 forintos kötet különböző könyv. Nem az áraknak, hanem a kiválasztott könyveknek kell különbözniük.

A mellékelt fájllal 10001 forintos keretre nincs megoldás: az összes ár 100-zal osztható, így három könyv árának összege is az.

A könyvcímek forrása

A magyar címeket a Typotex Kiadó szerzői oldalán és annak második oldalán ellenőriztük. A további, angol című kötetek a Raymond Smullyan Society könyvjegyzékéből származnak. Minden felsorolt könyv Raymond M. Smullyan műve; ezért a bemeneti fájlban nincs külön szerzőoszlop.