Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A KöMaL 2012. októberi informatika feladatai

Kérjük, ha még nem tetted meg, olvasd el a versenykiírást.


Feladat típusok elrejtése/megmutatása:


I-jelű feladatok

A beküldési határidő 2012. november 12-én LEJÁRT.


I. 301. A világon sokfelé létezik olyan webhely, amely felhasználóik könyveinek csereberéjét hivatott segíteni. Hazánkban is próbálkoznak ilyennel www.rukkola.hu, de a sikeres működéshez kellően sok felhasználó szükséges. A regisztrálók bejelölhetik, mely könyveket ajánlják fel és mely könyveket igénylik. A weblap segít az igények kielégítésében az ajánlatok alapján.

A honlapunkról letölthető csere.txt állomány az ajánlatok és igények adatait tartalmazza időrendben, soronként egynek-egynek a rögzítésével. A soron belül az egyes értékeket pontosan egy szóköz választja el. Az első érték az adott könyvvel kapcsolatos művelet (A - ajánlat, I - igény), majd a rögzítés napja (a szolgáltatás indulásától számított napok száma, legfeljebb 100) szerepel, aztán a könyv, végül a felhasználó azonosítója (mindkettő legfeljebb 200) látszik. (A könyvazonosító nem egy konkrét példányt jelöl, hanem a tartalmat határozza meg.) A fájlban legfeljebb 2000 adatsor található.

A csere.txt állomány első néhány sora:

A 1 83 1
A 1 63 3
I 1 61 11
I 2 63 8
...

Írjunk programot (i301.pas, i301.cpp, ...) néven, amely megoldja az alábbi feladatokat. Az egyes feladatok megoldása előtt jelenítsünk meg a képernyőn a feladat sorszámát tartalmazó szöveget (például: 4. feladat), a beolvasás előtt pedig a beolvasás tartalmára vonatkozó üzenetet (például: ,,Add meg egy könyv azonosítóját!''). Az ékezet nélküli kiírás is megengedett.

[1.] Olvassuk be és tároljuk el a csere.txt állomány adatait a későbbi feladatok megoldásához szükséges formában.

[2.] Írjuk a képernyőre a fájlban található igénylések és ajánlatok darabszámát.

[3.] Kérjük be egy könyv azonosítóját és írjuk a képernyőre, ki és mikor igényelte először. Ha ezt a könyvet még nem igényelte senki, akkor az ,,Ez a könyv még nem szerepelt igénylésben.'' szöveget írjuk ki.

[4.] Írjuk a legnépszerűbb (legtöbb személy által igényelt) könyv azonosítóját a képernyőre. Ha ,,holtverseny'' alakul ki, mindet jelenítsük meg, egymástól szóközzel elválasztva. Az azonosító mögött zárójelben tüntessük fel az igénylők számát is. Például: 18 (21) 3 (21).

[5.] Azt mondják, hogy az ilyen weblapokon mindenki több könyvet szerepeltet az igénylési listáján, mint amennyit felajánl. Vajon ez tényleg így van? Határozzuk meg a rendelkezésre álló adatok alapján, hogy kik azok, akik legalább annyi könyvet igényelnek, mint amennyit felajánlanak. Jelenítsük meg a képernyőn az ő azonosítójukat egy sorban, egymástól egy-egy szóközzel elválasztva.

[6.] Az igényléseket olyan módon állítják párba az ajánlatokkal, hogy az első igénylőhöz juttatják el az adott könyv első felajánlott példányát. Írjuk a képernyőre annak a könyvnek az azonosítóját, amely először talált új gazdára, valamint azt, hogy hány napot kellett várnia az igénylőnek erre.

[7.] Határozzuk meg a könyvek útját. Rögzítsük a mozgas.txt fájlban soronként az egyes ,,könyvmozgásokat''. A sor első eleme a nap sorszáma legyen, amikor sikerült megtalálni az igénylés párját, azaz amikor egy könyv ajánlata és igénye párba került. A második helyen a könyv azonosítója szerepeljen, aztán a felajánló, majd végül az igénylő sorszáma álljon. A soron belül ezeket az értékeket egy-egy tabulátorral válasszuk el egymástól. A fájlon belül a megjelenítés sorrendje tetszőleges lehet.

Beküldendő a program forráskódja (i301.pas, i301.cpp, ...), valamint a program rövid dokumentációja (i301.txt, i301.pdf, ...), amely megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

Letölthető fájl: csere.txt

(10 pont)

megoldás, statisztika


I. 302. A póker igen népszerű játék. Az osztás során az egy játékosnak jutó lapokat táblázatkezelő program segítségével állítjuk elő véletlenszerűen. Az előállítás mellett meg kell mondanunk, hogy az adott lapsorozatnak mi a kártyakombináció neve pókerben.

A lapok az A2:A6 tartományban álljanak elő a francia kártyán található jelölésekkel és színekkel, tehát például a kőr ász lap esetén a megfelelő cellában piros színnel jelenjen meg. A lapsorozat kártya értéke - amennyiben van neve - az A1 cellába kerüljön.

A lapsorozatok kártya értékeiről a

http://hu.wikipedia.org/wiki/Kártyakombinációk_(póker)

oldalon tájékozódhatunk.

A megoldás során tetszőleges számú segédcella használható, de saját függvény és makró használata tilos.

Beküldendő a megoldást adó munkafüzet (i302.xls, i302.ods, ...), a használt program verziószámát és a megoldás lényegét tartalmazó leírás (i302.txt, i302.pdf, ...) egy fájlba tömörítve (i302.zip).

(10 pont)

statisztika


I. 303. Készítsük el egy utca egyik oldalának egyszerű tervrajzát a tervet tartalmazó lista alapján Imagine Logo programozási környezetben.

Készítsük el a ház :m, a háztömb :m :hsz, a zebra :m és a park :m eljárásokat. Ezeket felhasználva a következő, utcát rajzoló utca :sor :m eljárást írjuk meg, ahol az :m a méretet, a :sor az utca felépítését meghatározó listát határozza meg.

A háztömböt, illetve a parkot járda veszi körül. A színeket tetszőlegesen választhatjuk meg.

Az utca tervét tartalmazó lista elemei:

hx - háztömb, ahol x 1 és 9 közötti egész szám;
z  - zebra;
p  - park.

A megoldás során csak a programozási nyelv automata és funkcionális részét használjuk. Ne alkalmazzunk változókat, csak paraméterezést.

Beküldendő a program projektállománya, forráskódja (i303.imp).

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2012. november 12-én LEJÁRT.


S. 74. Atommeghajtású űrhajónkkal szeretnénk eljutni egy másik csillagrendszerbe úgy, hogy a lehető legtöbb titánnal érkezzünk meg. Van egy térképünk az ismert csillagrendszerekről, melyek között kizárólag egyirányú féregjáratokon tudunk közlekedni. A féregjáratrendszer jelenlegi állapotában teljesül minden csillagrendszerre, hogy ha kilépünk belőle, akkor biztosan nem tudunk visszajutni.

Minden csillagrendszerről tudjuk, hogy mennyi uránt (melyet üzemanyagként használunk), illetve titánt tudunk bányászni, ha meglátogatjuk. Az urán tárolása körülményes, ezért csak meghatározott mennyiséget tudunk belőle raktározni. Minden féregjáratról tudjuk, hogy mennyi uránt fogyasztunk az áthaladás közben. Szerencsére bármely csillagrendszerben feltölthetjük uránkészletünket egy egységnyi titánért. Kezdetben tele van az üzemanyagtartályunk, és nincs titánunk.

Írjunk programot, amely a standard inputról beolvassa a térképet, valamint az induló- és a célcsillagrendszer sorszámát, és megadja, hogy legföljebb mennyi titánnal érhetünk el a célba, továbbá az ehhez szükséges útvonalat is.

Bemenet: A standard input első sorában öt szám található, szóközökkel elválasztva: a csillagrendszerek (2\le N\le 10\;000) száma, a féregjáratok (1\le
M\le 200\;000) száma, az induló- és a célcsillagrendszer sorszáma (a csillagrendszereket 1-től N-ig sorszámozzuk), valamint az üzemanyagtartályunk (1\le K\le 1\;000\;000) kapacitása.

A következő N sor rendre az 1,2, \ldots, N-edik csillagrendszert írja le két, szóközzel elválasztott egész számmal, melyek megadják a bányászható titán és urán mennyiségét (0\le T,U\le 1\;000\;000). Az utolsó M sor rendre az 1,2, \ldots,
 M-edik féregjáratot írja le három egész számmal, melyek a járat kezdő- és célcsillagrendszerének sorszáma és az áthaladáshoz szükséges urán mennyisége (0\le
 W\le 1\;000\;000).

Feltehetjük, hogy a kezdő- és célcsillagrendszer nem esik egybe, valamint, hogy nincs két olyan féregjárat, melyek ugyanazt a két csillagrendszert kötik össze, továbbá, hogy a féregjáratok kezdő- és végpontja sem esik egybe.

Kimenet: A program írja ki a standard kimenet első sorába, hogy maximum mennyi titánnal érkezhetünk meg célunkhoz. A második sorba írjunk ki egy ehhez szükséges útvonalat is, a következő formában: az első szám legyen az útvonalban szereplő csillagrendszerek száma (beleértve a kezdő- és célcsillagrendszert), aztán az úton szereplő csillagrendszerek sorszámának felsorolása következzen.

Amennyiben nem juthatunk el a célig, akkor a standard kimenet egyetlen sorába a -1 szám kerüljön.

Példák:

Pontozás: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 2 pontot ér. A programra akkor kapható meg a maximális 8 pont, ha bármilyen, a feltételeknek megfelelő tesztesetet képes megoldani a 3 mp futási időlimiten belül. Kapható részpontszám, ha a program csak kisebb tesztesetekre tud lefutni időben, továbbá akkor is, ha a program csak olyan teszteseteket tud megoldani, amelyeknél a féregjáratokon való áthaladáshoz szükséges üzemanyag mennyisége mindig 0.

Beküldendő egy tömörített s74.zip állományban a program forráskódja (s74.pas, s74.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s74.txt, s74.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrás mely fejlesztői környezetben fordítható.

Példa be- és kimenetek: s74.zip

Danner Gábor ötlete alapján

(10 pont)

megoldás, statisztika


Figyelem!

Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.