Programozó Bajnokság 2009
2009. március 25.
MPB 2009 Az alábbiakban a Szabolcs-Szatmár-Bereg Megyei Önkormányzat Megyei Pedagógiai, Közművelődési és Képzési Intézete, valamint a Széchenyi István Közgazdasági Szakközépiskola által szervezett Megyei Programozó Bajnokság döntőjének feladatait adtuk meg. A megoldáshoz 3 óra áll rendelkezésre, mely közben a számítógépre telepített fejlesztőeszköz helpjén kívül más segédeszköz nem használható. Az elkészült munkákat a G:\ maghajtóra kell elmentened, az esetleges forrásokat a K:\ meghajtón találod. A feladatokat olvasd át, mielőtt nekikezdenél a megoldásoknak. A feladatok sorrendje nem feltétlenül tükrözi azok nehézségi szintjét! Az állományok neveit tetszőlegesen választhatod, ha más utasítást nem tartalmaz a feladat szövege, de utaljon a feladat tartalmára! A megoldásokhoz tetszőleges mennyiségű piszkozat használható, azokat a verseny végén, ezzel a feladatlappal együtt, magaddal viheted. Adatbekéréskor és képernyőre történő íráskor egész, a magyar nyelv szabályait követő, mondatban tájékoztasd a felhasználót!
A királyi lottójáték Tarbolin egykori uralkodója IV. Gandelfin látván a kincstár kongó ürességét lottójátékot szervezett. Ezzel bevételhez jutott, másrészt az alattvalók morálját is növelte valamelyest. A játékot kéthetente rendezték és 60 számból választottak ki 4-et. Minden alattvaló egyetlen szelvénnyel játszhatott, amit hetente érvényesíttetnie kellett. Aki ezt elmulasztotta, az adott heti húzáson nem nyerhetett. A szelvényeket központilag osztották ki, ügyelve, hogy ne lehessen két egyforma. A játék során csak a telitalálatos szelvény és a 3-om találatos szelvények nyernek. Berumbil, Gandelfin leszármazottja is továbbvitte őse hagyományát és elrendelte, hogy az eddig kihúzott számokat rögzítsék le és bárki szabadon hozzáférhessen. A feladat ezekkel a lottószámokkal kapcsolatos. 1. Hozd létre az állományt, amelyben a lottószámok vannak. Az utolsó húzás a 2009. volt. A file soronként tartalmaz egy húzást, először a húzás sorszáma, majd a kihúzott számok következnek. Az adatok szóközzel elválasztottak, az alábbi minta szerint: 2008 15 24 34 45 2009 23 24 35 58 A számok mindig növekvően vannak megadva és soha nem fordult elő, hogy kétszer ugyanaz az ember nyerte volna meg a 4 találatért járó jutalmat! Ezt a feladatot is programmal old meg, az adat állomány neve legyen lotto.dat, a programod berumbil néven mentsd el! Érd el, ha az adatállományod már létezik, akkor ne generáljon újabb adatokat a programod!
- 1/5 -
Programozó Bajnokság 2009
2009. március 25.
Berumbil maga is igen szereti a matematikát és a töménytelen szám láttán állandóan újabb és újabb ötletek merültek fel benne. Segíts megválaszolni Berumbilnak a következő kérdéseket programoddal. A válaszok előtt jelenítsd meg, melyik kérdésre adod meg a választ. A válaszok között hagyj egy üres sort! Ha a billentyűzetről kérsz be adatot, mindig írd ki milyen adatokat vársz a felhasználótól! 2. Berumbil is örökölt apjától egy szelvényt, ahogy szerte a birodalomban apáról fiúra száll a szelvény. Állapítsd meg, hogy Berumbil szelvényével nyertek-e már valamikor. Ha igen írasd ki az összes eseményt és a találatok számát is. Nyeretlen szelvény esetén is adj felvilágosítást! Berumbil számait kérd be billentyűzetről! 3. Berumbil kedvencei a különleges számok és a különleges alakzatok. Számold meg, hányszor fordult már elő, hogy csak prím számokkal nyerte meg valaki a főnyereményt, majd az eredményt írasd ki a képernyőre! 4. Berumbil szerencseszáma a 101. Határozd meg, hányszor fordult elő, hogy a húzott számok összege éppen ez a szerencseszám. Add meg melyik húzásnál fordult elő legelőször és melyik volt a legutolsó ilyen húzás! 5. A 60 számot a szelvényekre a következők szerint írták fel: 1
11 21 31 41 51
2
12 22 32 42 52
3
13 23 33 43 53
4
14 24 34 44 54
5
15 25 35 45 55
6
16 26 36 46 56
7
17 27 37 47 57
8
18 28 38 48 58
9
19 29 39 49 59
10 20 30 40 50 60 A nyerőszámokat inverz módon emelik ki a szelvényeken. Számold össze, hányszor fordult elő, hogy a fenti mintának megfelelően, a kihúzott számok egy téglalap négy csúcsát alkották! 6. Berumbil a matematika mellett a sakk játékot is igazán szerette. Uralkodásának kezdetekor, ami az 1848. húzást követően történt, kihirdette, hogy akinek a 4 száma úgy helyezkedik el a szelvényen, hogy a huszár az egyikből kiindulva, szabályos lépésekkel visszajut a kiinduló helyre, azok nyertes szelvény esetén egy újabb szelvényt kapnak a királytól. (tehát 3 találat esetén is) Az alábbi szelvény egy ilyen elhelyezkedést mutat be és egy lehetséges útvonal a 45-24-12-33-45: - 2/5 -
Programozó Bajnokság 2009
2009. március 25.
1
11 21 31 41 51
2
12 22 32 42 52
3
13 23 33 43 53
4
14 24 34 44 54
5
15 25 35 45 55
6
16 26 36 46 56
7
17 27 37 47 57
8
18 28 38 48 58
9
19 29 39 49 59
10 20 30 40 50 60 Programoddal add meg, hányszor fordult elő, hogy valaki extra szelvényhez jutott ezen a módon!
Halászat Berumbil az egyik országjárása idején egy furcsa problémával találta magát szembe. Egy halászattal foglalkozó faluban 25 család él. A halászatok alkalmával a zsákmányt ládákba teszik és a halászat végén a parton egymás után helyezik el őket. A ládákat lemérik, tehát a bennük lévő halak tömegét tudják. Az elosztás úgy történik, hogy az első család kap valamennyi ládát a sor elejéről, majd a második család a maradék sor elejéről, végül az utolsó családé a maradék néhány láda. A feladat az, hogy úgy kell elosztani a ládákat, hogy minden család igazságosan részesüljön a zsákmányból, azaz annyi ládát kapjon mindenki, hogy a ládákban lévő halak összsúlya között a lehető legkisebb legyen az eltérés. A ládák sorrendjét nem lehet megváltoztatni. Berumbil az udvari programozókat kérte fel a feladat megoldására Segíts nekik megoldani a problémát! Berumbil szeretné, ha más településeken is használható lenne a program ezért a családok számát is kérd be és ez alapján dolgozz. A legnagyobb halásztelepülésen sem él több mint 100 család és a legkisebben is többen élnek, mint 10. A ládák száma változó, de nem haladja meg a 8000-et egyik településen sem. A ládákban a halak tömege 10 és 25 kg között van. (Minden hajón a halászat végén az utolsó láda tartalmát visszaadják a tengernek, ha a benne lévő halak tömege kevesebb, mint 10 kg.) A ládák és családok számát kérd be és ellenőrizd le, hogy megfelelő értéket kapott-e a program. (Berumbil, ha a zsákmány kevesebb ládában fér el, mint a családok számának négyszerese, a királyi halászflotta zsákmányából egészíti ki a családok számának négyszeresére a - 3/5 -
Programozó Bajnokság 2009
2009. március 25.
ládák számát.) Véletlenszám-generátorral töltsd fel a ládákban található halak súlyát, ügyelve, hogy egy ládában akár 22,45kg hal is lehet. Ezen adatok alapján add meg azt a felosztást, amellyel minden család elégedett lenne az adott településen! Az eredményt a következő formában írd ki a képernyőre: 1. család: 1-9-es ládák; összsúly 138.7kg 2. család: 10-15-es ládák; összsúly 141,3kg A tömeget egy tizedes pontossággal jelenítsd meg!
A várfal javítása Tarbolin történelme nem mentes a háborúktól sem. Nagy Terpin király volt Tarbolin utolsó hadviselő királya. Uralkodását békével fejezte be és azóta is béke honol Tarbolinban. A béke kiharcolása azonban nem volt egyszerű. A szomszédos Kerix birodalom Armin nevű uralkodója folyamatosan zaklatta Nagy Terpin végvárait. A háborúk alatt a végvárak javítása nagyon fontos volt és a nyersanyagoknak is híján voltak. Armin napközben lövette Terpin várait, de az éjszakák alatt a fegyverek elnémultak. Ekkor volt idejük a birodalmi építészeknek a keletkezett hibák gyors kijavítására. A faljavító munkásokat erősen korlátozta az éjszaka, ezért csak kör alakú területet tudtak kijavítani egy falfelületen és alkalmanként. (Egy falrészen, ha dolgoztak az összes hibát egy kör alakú javítással hozták helyre.) A kijavítandó kör alakú terület sugarának olyannak kell lenni, hogy az adott várfal minden lövedék találati helyét lefedje. Nagy Terpin király az udvari programozókat hívta segítségül a feladat támogatásához. A vár minden síkfelületű falának bal alsó sarkához egy Descartes-féle derékszögű koordináta rendszert rögzítettek és ebben a koordináta rendszerben a lövedékek találati helyeit, mint a sík egy pontját írták le. Egy falfelületre eső találatokat a lyukakxy.dat állományban tárolják, soronként az első szám a találati hely X koordinátáját, a második szám az Y koordinátáját jelenti pontosvessző (;) karakterrel elválasztva. Az állomány névben az xy a falrész azonosítója. A 07-es azonosítójú falhoz tartozó adathalmazt a lyukak07.dat állományban találod a források között. A megoldásodnak nem szabad csak erre az egy állományra korlátozódni. Bizonyos falfelületek esetén a felmért találatok száma igen magas is lehet, akár több mint, amit Tarbolin számítógépei memóriájukban tárolni tudnak! Írd meg a varfal nevű programot amelyben a következő kérdésekre adsz választ:
- 4/5 -
Programozó Bajnokság 2009
2009. március 25.
1. Kérd be egy koordináta-pár sorszámát, megadva a választási lehetőség nagyságát is. Add meg, ha ezt a pontot választanánk középpontnak, mekkora lenne a minimális kör sugara, amivel a szükséges falrészt kijavíthatnák a munkások! 2. Határozd meg annak a találatnak (pontnak) a koordinátáit, mint a javítási kör középpontját, és a hozzá tartozó kör sugarát, amelyik a legkisebb felületű javítást igényli a királyi építészektől! Ne feledd, a programnak minden falfelület hibáira működni kell! Minden falhoz más és más lyukakxy.dat állomány tartozik! Az alábbi képen egy javítás látható, ami nem feltétlenül optimális. A kör középpontját egy karikával megjelöltük. Ha egy pontot az (a;b) koordinátákkal, egy másikat a (c;d) koordinátákkal adtunk meg akkor a két pont távolsága: d =
(a − c )2 + (b − d )2
- 5/5 -
