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 2018. szeptemberi 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ő 2018. október 10-én LEJÁRT.


I. 460. Egy téglalap alakú üveglapra gondolatban egy \(\displaystyle N\times M\)-es (\(\displaystyle 10\le N, M\le 10\,000\)) négyzethálót helyezünk. Az üveglapot rá merőlegesen \(\displaystyle P\) (\(\displaystyle 0\le P\le N\times M\)) pontban egy-egy nem polarizált fénysugárral megvilágítjuk úgy, hogy minden fénysugár pontosan egy négyzetre essen. Az üveglapra \(\displaystyle K\) (\(\displaystyle 0\le K\le 1\,000\)) darab különböző szélességű és hosszúságú, téglalap alakú polárszűrőt helyezünk el úgy, hogy oldalaik a négyzetháló rácsvonalaira esnek. A polárszűrők érintkezhetnek és átfedhetik egymást, de a lapról nem lóghatnak le. Kétféle polárszűrő van: az egyik a beérkező fényt az üveglap felső oldalával párhuzamosan, a másik arra merőlegesen polarizálja. Az a fénysugár, amely két, egymásra merőlegesen polarizáló polárszűrőre esik, nem jut át az üveglapon.

Készítsünk programot i460 néven, amely a következő problémákat oldja meg.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et, \(\displaystyle M\)-et, \(\displaystyle P\)-t és \(\displaystyle K\)-t. A következő \(\displaystyle P\) sorból a megvilágított négyzetek bal alsó sarkának koordinátáit, utána \(\displaystyle K\) sorból a polárszűrők bal alsó, illetve jobb felső sarkának koordinátáit és a polarizációt (\(\displaystyle p\) vagy \(\displaystyle m\)). A koordináták egész számok, az üveglap bal alsó sarkának koordinátái \(\displaystyle 1,1\). A program írja a standard output egymás utáni három sorába a következő feladatok megoldását:

– soroljuk fel a beolvasás sorrendjében azoknak a fényforrásoknak a sorszámát, amelyek fénye nem jut át az üveglapon a polárszűrők miatt;

– adjuk meg, hány olyan négyzet van, amelyet nem világítunk meg, de a polárszűrők miatt nem átlátszó;

– adjuk meg, melyek azok a polárszűrők, amelyeket eltávolítva a fénysugarak átlépése nem változik (több lehetséges megoldás esetén elég egyet megadni).

Példa:

Beküldendő egy tömörített i460.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

statisztika


I. 461. (É). Hanna és Panna palacsintázót üzemeltet. Szeretnének mindenkit friss palacsintával kiszolgálni, ezért a hozzávalókat egész napra előre elkészítik, és a palacsintát magát akkor sütik, ha valaki éppen kér. A vevő belép az üzletbe, rendel, és rendelését – a többiek rendelésének teljesítése után – azonnal elkészítik.

Feladatunk, hogy ezt a folyamatot táblázatkezelővel modellezzük. Ehhez egy munkafüzet négy munkalapját használjuk. A Vásárlás munkalap tartalmazza a vevő érkezési idejét, a rendelés adatait, a fizetett összeget és a kiszolgálás időpontját. A Palacsinták munkalapon a palacsinták ízesítése, ára és az a darabszám szerepel, amennyihez elegendő töltelék áll rendelkezésre. Az Üzleti adatok munkalap tartalmazza a nyitás és zárás időpontját, valamint a Vásárlás munkalap kapcsán lentebb említett \(\displaystyle T\), \(\displaystyle Db\), \(\displaystyle t\) értékeket. A Segéd munkalapon a feladat megoldásához szükséges segédszámításokat végezhetjük.

A Vásárlás munkalap kitöltését az alábbiak szerint készítsük, legfeljebb 1000 vásárlóra számítva:

1. Az érkezés oszlopban a vevők belépési időpontja szerepel. Az időpontokat véletlenszerűen állítsuk elő. A vevők nyitástól zárásig legfeljebb másodpercnyi sűrűséggel követhetik egymást, de feltételezhetjük, hogy \(\displaystyle T\) percnél tovább nem marad új vásárló nélkül az üzlet.

2. A darabszám oszlop a vevő által rendelt mennyiséget tartalmazza. Egy vevő csak egyfajta palacsintát kérhet, abból is legfeljebb \(\displaystyle Db\) darabot. Értékét véletlenszerűen kell előállítanunk.

3. Az ízesítés oszlopban jelenjen meg, hogy milyen ízesítésűt választott. Értékét véletlenszerűen állítsuk elő úgy, hogy a Palacsinta munkalapon szereplő minden ízesítésnek azonos valószínűsége legyen.

4. A fizetés oszlopban a rendelt darabszámtól és ízesítéstől függő értéket kell megjelenítenünk. Figyelembe kell vennünk azonban, hogy ha az adott ízesítésű palacsintához már nem áll rendelkezésre elegendő töltelék, akkor csak az elkészített palacsinták után fizet a vevő.

5. A kiszolgálás oszlopban a kiszolgálás időpontját kell meghatároznunk az alábbiak ismeretében. A palacsintákat egyesével, egymás után sütik. Egy palacsinta elkészítéséhez szükséges idő \(\displaystyle t\) másodperc. Sütése akkor kezdődik el, ha minden korábbi vevő kiszolgálása megtörtént. A betérő vásárló biztosan kivárja a sorát, valamint ha zárás előtt lépett az üzletbe, biztosan kiszolgálják. A rendelés, fizetés időigényétől eltekintünk.

6. A Vásárlás munkalapon csak a zárás előtt érkező vásárlók sorainak adatai jelenjenek meg. Annak a vásárlónak a sora, aki utoljára kapott a választott ízesítésből, sárga, akit pedig egyáltalán nem tudtak kiszolgálni, szürke háttérrel látszódjon.

A számítások során egész másodpercekkel dolgozzunk, a számot tartalmazó cellákban egész értékek szerepeljenek.

Beküldendő egy i461.zip tömörített állományban a megoldást tartalmazó i461 munkafüzet és a dokumentációt magában foglaló i461.pdf fájl. A dokumentáció tartalmazza a használt táblázatkezelő nevét és verziószámát.

(10 pont)


I. 462. Az irodai munkában gyakran előfordul, hogy ugyanazt a részfeladatot számtalanszor kell végrehajtani. A ,,rabszolgamunka'' automatizálásával sok időt lehet megspórolni. Egy ilyen gyakran ismétlődő probléma, hogy egy munkafüzet lapjain található adatok alapján kell diagramot készíteni.

Jelen feladatban legfeljebb 100 munkalappal kell dolgoznunk. Minden munkalap első sora tartalmazza a kategóriák nevét, az első oszlop pedig az adatsorok feliratát. A munkalapok legfeljebb 12 sornyi és 12 oszlopnyi adatot tartalmaznak. Az összes munkalapra kell készítenünk egy halmozott oszlopdiagramot az ott található adatokból. A diagram címe az A1-es cella tartalma legyen. Az összes diagramot egyetlen makróindítással kell elkészítenünk.

Beküldendő egy i462.zip tömörített állományban a megoldást tartalmazó i462 munkafüzet és a dokumentációt magában foglaló i462.pdf fájl. A dokumentáció tartalmazza a használt táblázatkezelő nevét, verziószámát és a megoldást jelentő makró(k) lényeges elemeinek magyarázatát és indításának módját.

(10 pont)


I/S-jelű feladatok

A beküldési határidő 2018. október 10-én LEJÁRT.


I/S. 28. Egy hatalmas telken sportkomplexumot terveznek. A telekre gondolatban egy koordináta-rendszert helyeznek. A kialakítandó \(\displaystyle N\) darab sportpálya mind téglalap alakú, oldalaik a koordináta-rendszer tengelyeivel párhuzamosak. Ismerjük minden pálya két szemközti csúcsának koordinátáit. A pályáknak nincs közös területe, de oldalaik érintkezhetnek egymással. A tervek szerint két pálya között pontosan akkor készül majd átjáró, ha legalább \(\displaystyle D\) hosszú szakaszon érintkeznek egymással. Egy pálya egy oldalát a vele érintkező más pályák több szakaszra osztják (ha nem, akkor a teljes oldalt egy szakasznak tekintjük). Vegyük azokat a szakaszokat, amik a külső térre néznek, vagyis nem részei más pálya oldalának. Egy-egy ilyen, legalább \(\displaystyle D\) hosszú szakaszra bejáratot terveznek. Adjuk meg, hogy a sportkomplexum tervében összesen hány bejárat és hány átjáró van.

Bemenet: az első sor a pályák \(\displaystyle N\) számát és a \(\displaystyle D\) hosszúságot tartalmazza. A következő \(\displaystyle N\) sor mindegyike négy egész számot tartalmaz: egy-egy pálya két szemközti csúcsának koordinátáit.

Kimenet: egy sorba írjuk ki az átjárók, aztán a bejáratok számát.

Bemenet (a / jel sortörést helyettesít) Kimenet
9 2
2 8 10 4 / 7 13 9 8 / 9 9 12 8 / 10 6 12 4 / 12 10 14 2
9 14 15 10 / 2 11 7 8 / 3 4 5 2 / 7 4 9 3
9 22

Korlátok: \(\displaystyle 1\le N\le {10}^{5}\),
\(\displaystyle -{10}^{9}\le \text{koordináták}\le {10}^{9}\),
\(\displaystyle 1\le D\le {10}^{9}\), egész számok.

Értékelés: a pontok 20%-a kapható, ha \(\displaystyle D=1\); további 20% kapható, ha a pályák \(\displaystyle 1\times 1\)-es négyzetek; további 20% kapható, ha \(\displaystyle N\le 1000\); további 40% kapható az eredeti korlátokra.

Időlimit: 0,3 mp, memórialimit: 100 MiB.

Az I/S és S-jelű feladatok megoldását a http://mester.inf.elte.hu automatikus értékelő rendszer segítségével kipróbálhatod, tesztelheted (Téma: KöMaL - 2018/19).

(10 pont)

statisztika


S-jelű feladatok

A beküldési határidő 2018. október 10-én LEJÁRT.


S. 127. Egy országban \(\displaystyle N\) darab város van, amiket kétirányú utak kötnek össze. Az úthálózatra teljesül, hogy bármelyik városból bármelyikbe el lehet jutni. Két város között legfeljebb egy közvetlen út van. Minden útra adott egy súlykorlátozás, hogy rakománnyal együtt legfeljebb mekkora tömegű teherautó mehet rajta. Egy áruszállító cég nyersanyagokat szállít városok között. A cégnek nem számít, hogy két város között a szállítás milyen hosszú úton történik, de a lehető legtöbb nyersanyagot szeretnék elvinni egy-egy teherautóval. Adott \(\displaystyle Q\) darab várospár, amik között nyersanyagot kell szállítani. Minden várospárra adjuk meg, hogy legfeljebb milyen nehéz lehet a teherautó szállítmánnyal.

Bemenet: az első sor tartalmazza a városok \(\displaystyle N\) számát, az utak \(\displaystyle M\) számát és a várospárok \(\displaystyle Q\) számát. A városokat 0-tól \(\displaystyle (N-1)\)-ig indexeljük. A következő \(\displaystyle M\) sor mindegyike három számot tartalmaz: egy adott út mely városokat köt össze, és mekkora rá a súlykorlátozás. A következő \(\displaystyle Q\) sor mindegyike két számot tartalmaz: egy adott várospár indexeit, amik között szállítani kell.

Kimenet: \(\displaystyle Q\) sor mindegyikébe egy számot írjunk: azt a maximális súlyt, amilyen nehéz teherautó indulhat az adott várospár között.

Korlátok: \(\displaystyle 2\le N, Q\le {10}^{5}\), \(\displaystyle N-1\le M\le 5\cdot {10}^{5}\), \(\displaystyle 1\le \text{súlykorlátok}\le {10}^{9}\), egész számok.

Értékelés: a pontok 20%-a kapható, ha egy útra a súlykorlát csak 1 vagy 2 lehet; további 20% kapható, ha \(\displaystyle N\le 100\); további 20% kapható, ha \(\displaystyle M\cdot Q\le {10}^{6}\); további 40% kapható az eredeti korlátokra.

Időlimit: 0,7 mp, memórialimit: 100 MiB.

Az I/S és S-jelű feladatok megoldását a http://mester.inf.elte.hu automatikus értékelő rendszer segítségével kipróbálhatod, tesztelheted (Téma: KöMaL - 2018/19).

(10 pont)

statisztika


Figyelem!

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