Utolsó módosítás: 2008. december 5.
Ez a feladatsor a második verseny harmadik, december 5. péntek délutáni turnusához tartozik.
Le lehet tölteni az összes példa be- és kimenetet és példa forráskódot egyben: z5p.tgz vagy z5p.zip.
A feladatok nem feltétlenül nehézségi sorrendben vannak.
Ebben a feladatban számok egy listájának súlyozott összegét kell kiszámolni, ahol a súly az adott tag indexe (egytől számítva).
A program bemenete egy sor, amiben pontosan tizennégy (14) szám áll szóközzel elválasztva, mondjuk a0, a1, … a14. Mindegyik szám legfeljebb háromjegyű nemnegatív egész, és lehetnek köztük egyenlőek is.
A program kimenete egy sorból áll, ebben egyetlen szám, mégpedig az 1·a0 + 2·a1 + … + 14·a14 súlyozott összeg. (A sor után kell újsor jelet írni.) Az egyes számok súlya tehát eggyel nagyobb, mint az indexük.
Például ha a bemenet
48 69 17 57 90 88 53 40 57 0 9 44 26 32
akkor a kimenet
4060
Több példa:
Ebben a programban tíz pont által kifeszített 120 háromszög közül kell megkeresni a legkisebb területűt.
A program bemenete tíz sorból áll, minden sorban két egész szám (legfeljebb négyjegyű nemnegatív számok), amik egy-egy síkbeli pont koordinátáit adják meg. A program megvizsgálja azon háromszögeket, amiknek a csúcsai ezen pontok közül kerülnek ki (két csúcs természetesen nem lehet ugyanaz a pont), kiszámolja a területüket, és kiírja a legkisebb terület kétszeresét (meg egy újsor jelet).
Ha egy háromszög három csúcsának koordinátája (x0, y0), (x1, y1), (x2, y2), akkor a terület kétszeresét a következő determináns abszolutértékeként számolhatjuk.
(A terület kétszerese mindig egész szám, mivel a csúcsok koordinátái egészek.)
Például lehet a bemenet a következő.
288 141 733 504 182 572 838 647 504 426 245 285 746 866 700 784 160 760 536 119Ekkor a legkisebb háromszög csúcsai az (504, 426), (746, 866), (700,784), a kimenet pedig ennek a kétszeres területe.
396
Még pár példa.
Egy automatába több pénzt dobtak be, mint amennyibe a vásárolt áru kerül. Az automata külön rekeszekben tartja a 100, 50, 20, és 10 forintos érméket, így pontosan tud visszaadni. Az ön feladata megadni, milyen érméket kell kidobnia az automatának.
Az automata úgy dolgozik, hogy az árkülönbözetből mindig a lehető legnagyobb érmét adja vissza a négy rendelkezésre álló érme közül. Mindegyik érméből elég sok van, feltehetjük, hogy nem fogynak el. Az áruk ára és a bedobott összeg is mindig osztható 10 forinttal (a gép nem fogad el kisebb érmét).
A program bemenete két sorból áll, mindkettőben egy egész szám (nemnegatív, legfeljebb négyjegyű). Az első sor a vásárolt termék ára, a második a bedobott pénzek értéke. Az utóbbi szám mindig nagyobb az előbbinél.
A kimenet minden sorában egy érme értéke áll, ami tehát lehet 100, 50, 20, vagy 10. Az érméket olyan sorrendben kell felsorolni, ahogy a gép kiadja őket, vagyis először a nagyobbakat. Ha a gép egy fajta érméből többet is kidob, akkor azt többször kell kiírni a kimenetre.
Például ha a bemenet
210 740
akkor a kimenet
100 100 100 100 100 20 10
Felmérést végeztünk négy árucikkről (mondjuk kenyér, tej, tojás, cukor). Hét üzletet látogattunk meg, és mindegyikben felírtuk mind a négy árucikk árát. Az ön programjának minden árucikkről meg kell találnia, a boltok közül melyikben a legolcsóbb.
A program bemenete egy számtáblázat: hét sor mindegyikében négy egész szám áll. (Mindegyik szám nemnegatív és legfeljebb ötjegyű. Minden bolthoz egy sor tartozik, minden árufajtához egy oszlop.)
A program mind a négy oszlopban külön-külön megkeresi az ebben szereplő legkisebb számot (ez a bemenetekben egyértelmű). A program kimenete egy sorban négy egész szám, az egyes oszlopokban a minimális szám sorindexe. (A sorokat 0-tól számozzuk.)
Nézzünk egy példát. Legyen ez a bemenet.
51 2787 654 54 64 1898 377 55 69 2721 399 70 102 2131 329 67 42 2019 331 86 78 1245 51 85 48 2922 225 91
Az első oszlopban szerepel mondjuk a tojás ára. Ebből a legalacsonyabb a 42 forint, ami (nullától számítva) a 4 indexű boltban kapható. Hasonlóan a második oszlop a hús ára, amiből a legolcsóbb az 5 indexű boltban kapható, 1245 forintért. Így a kimenet a következő.
4 5 5 0
Több példa letölthető.
Ebben a játékban egy négyzetes táblába vízszintes rudakat ejtünk be felülről. A programnak ki kell számítania, melyik kő meddig esik, és kiírnia, ebből milyen ábra áll elő.
A játék egy tíz mező széles és tíz mező magas négyzetes táblán játszódik. Minden lépésben egy vízszintes rudat dobunk be a tábla tetején, a rúdról meg van adva, hányadik oszloptól hányadikig ér, és ezekben az oszlopokban addig esik lefelé, amíg valamelyik mezője bele nem ütközik vagy egy korábbi rúdba, vagy a tábla aljára.
A program bemenete pontosan tíz sorból áll, mindegyik egy bedobott rudat ad meg, a bedobás sorrendjében. Minden sorban két szám áll (szóközzel elválasztva), az első a bal oldali első oszlop, ahol a rúd kezdődik, az utolsó jobb oldalt az utolsó oszlop, ameddig a rúd elér. Az oszlopokat nullától számozzuk, a két megadott oszlop közül mindkettőben a rúdnak még van mezője.
A program szimulálja a megadott tíz lépést.
(Mivel tíz sor van és tíz rudat dobunk be, a tábla sosem telhet meg.)
A program kimenete tíz sor, amik a tábla tíz sorát írják le felülről lefelé.
Minden sorban tíz jel áll,
ami kukac (@), ha a mező teli, vagy pont (.) ha üres.
Nézzünk egy példát. Legyen a bemenet a következő.
5 6 2 9 0 8 2 2 4 7 2 3 3 6 0 7 8 9 3 4
Az első rúd persze legalulra esik, és az 5 indexűtől a 6 indexűig ér. Ekkor a táblázat így néz ki.
.......... .......... .......... .......... .......... .......... .......... .......... .......... .....AA...
A következő négy rúd mind eggyel magasabb helyre esik. Figyelem, a negyedik rúd nem esik le az alsó oszlopba, mert ugyan ott lenne hely neki, de a harmadik rúdba beleütközik, ezért nem tud odáig leesni!
.......... .......... .......... .......... .......... .......... ..D....... CCCCCCCCC. ..BBBBBBBB .....AA...
Az ötödik rúd le tud esni a negyedik rúd mellé, mert azok a mezők még nem foglaltak.
.......... .......... .......... .......... .......... .......... ..D.EEEE.. CCCCCCCCC. ..BBBBBBBB .....AA...
A következő három rúd megint új sorokba esik.
.......... .......... .......... HHHHHHHH.. ...GGGG... ..FF...... ..D.EEEE.. CCCCCCCCC. ..BBBBBBBB .....AA...
A kilencedik rúddal valami érdekes történik: ez le tud esni egészen alulról a negyedik sorba, mert az ő oszlopaiban a feljebbi sorok nyitottak.
.......... .......... .......... HHHHHHHH.. ...GGGG... ..FF...... ..D.EEEEII CCCCCCCCC. ..BBBBBBBB .....AA...
Végül a tizedik rúd megint fönt marad.
.......... .......... ...JJ..... HHHHHHHH.. ...GGGG... ..FF...... ..D.EEEEII CCCCCCCCC. ..BBBBBBBB .....AA...
Így aztán a program kimenete a következő (ebben már nem lehet megkülönböztetni az egyes rudakat).
.......... .......... ...@@..... @@@@@@@@.. ...@@@@... ..@@...... ..@.@@@@@@ @@@@@@@@@. ..@@@@@@@@ .....@@...
Van még pár példa is.
Ebben a feladatban egy vállalati telefonkönyvből kell kikeresni neveket.
A program bemenete két részből áll. Az első rész a telefonkönyvet adja meg: az első sorban a telefonkönyvben szereplő nevek N száma, a következő N sorban egy egy szóból álló név és egy négyjegyű telefon mellék áll (köztük egy szóköz). Előfordul, hogy több (alacsonyabb beosztású) dolgozó ugyanazon a telefonon osztozik. A bemenet második része a kikeresendő neveket adja meg: a második rész első sora egyetlen K számból áll, a következő K sorban egy-egy név a fentiek közül.
A program kikeresi a telefon mellékeket, amik a bemenet második részében szereplő K névhez tartoznak. A kimenet K sorból áll, mindegyikben csak a mellék száma áll. A kimenetben ugyanolyan sorrendben állnak a számok, amilyen sorrendben a bemenet második felében a megfelelő nevek.
Fontos, hogy a bemenet nagyon nagy is lehet: N legfeljebb 12000, K legfeljebb 6000. A megoldásnak a nagy bemenetre is le kell futnia ahhoz, hogy helyesnek számítson.
A programot ruby nyelven érdemes megírni.
Először egy asszociatív tömbbe (Hash) jegyezze a telefonkönyvet,
ahol a kulcsok a munkatársak nevei, az értékek a telefonszámok.
(Ha nem emlékszik, hogy működnek az asszociatív tömbök, az s2f6
mintafeladatnál van egy rövid magyarázat.)
Ezután az asszociatív tömbből a nevek alapján gyorsan ki tudja keresni a megfelelő bejegyzést.
(A bemenetről egy sort a
Íme egy példa bemenet.
10 Hajdu 1637 Sipos 7421 Pap 5454 Kovacs 4089 Pal 9417 Molnar 1251 Kocsis 3167 Katona 3899 Kiss 2167 Kerekes 2193 6 Kiss Molnar Pap Katona Kocsis Sipos
Erre a kimenet a következő.
2167 1251 5454 3899 3167 7421
Az első sor Kiss telefonszámát adja meg, a második sor Molnárét, stb.
Próbálja ki a nagyobb bemeneteket is — az utolsó a legnagyobb méretű.