A KöMaL 2018. októberi informatika feladatai

I-jelű feladatok A beküldési határidő 2018. november 12-én LEJÁRT.

I. 463. (É). Adott egy nagyméretű négyzethálós lap, amelynek \(\displaystyle O\) oszlopa és \(\displaystyle S\) sora van. A négyzetek csúcspontjainak koordinátái egész számok, a bal alsó sarok az origó, azaz a \(\displaystyle (0;0)\) koordinátájú pont. A lapon egy szikével bemetszéseket készítünk, amelyek párhuzamosak a lap valamelyik oldalával. A bemetszések végpontjai egész koordinátájú pontok. Tudjuk, hogy bemetszés nem indul és nem végződik a lap szélén.

A honlapunkról letölthető nhalo.txt szöveges állomány első sorában a négyzetháló méretét megadó \(\displaystyle O\) és \(\displaystyle S\) értékek találhatók. A következő sorban a bemetszések \(\displaystyle B\) száma szerepel. Az ezt követő \(\displaystyle B\) sor mindegyikében egy számnégyes található, amelyből az első számpár a bevágás egyik végpontja, a második pedig a bevágás másik végpontja. A számpárok első tagja az oszlop, a második a sor koordinátája. A számokat pontosan egy szóköz választja el egymástól, a számok egyike sem nagyobb, mint 1000.

Készítsünk programot, amely a lap méretének és a bemetszések adatainak ismeretében megoldja a következő feladatokat. Minden feladat megoldása előtt írjuk ki a feladat sorszámát, pl. ,,1. feladat:'', illetve a beolvasás és kiírás esetén röviden írjunk magyarázó szöveget. Az ékezetmentes kiírás is elfogadott.

1. feladat: Olvassuk be a szöveges állományból az adatokat, és tároljuk el későbbi feldolgozás céljából.

2. feladat: Írjuk ki a legkisebb sorszámú sort, amelyben nincs bemetszés, például a következő formában: ,,A legkisebb sorszámú bemetszés nélküli sor: 2''.

3. feladat: Adjuk meg annak a legkisebb téglalapnak a területét, amely az összes bemetszést tartalmazza. A kimenet például ,,A legkisebb, minden bemetszést tartalmazó téglalap területe: 48''.

4. feladat: Adjuk meg, hogy összesen hány pontban találkoznak merőlegesen bemetszések. A kimenet például ,,A metszések 10 helyen találkoznak merőlegesen''.

5. feladat: Kérjünk be a felhasználótól egy oszlopszámot, és adjuk meg, hogy az adott oszlop milyen hosszúságú része nem tartalmaz bemetszést.

6. feladat: Adjuk meg a bemetszések hosszának átlagát két tizedesjegy pontossággal megjelenítve, például ,,A metszések átlagos hossza 4,75''.

7. feladat (ez a részfeladat az emelt szintű érettségi programozási feladatoknál összetettebb, nehezebb): Hozzuk létre a sorok.txt szöveges állományt, amely a négyzetháló bemetszések utáni helyzetét mutatja a sorok szerint. A szöveges állomány \(\displaystyle S\) sort tartalmaz, elsőként a négyzetháló legfelső egységnégyzeteit, majd sorban az utána következő négyzeteket, végül a négyzetháló legalsó sorának négyzeteit írja le. Ha egy sorban nincs függőleges bemetszés, akkor abban csak a 0 szám szerepel. Egyébként annyi egész van benne, ahány függőleges bemetszést ejtettek a sorban. Ilyenkor az egészek oszlopok szerint növekvő sorrendben mutatják a sor összefüggő, nem szétvágott négyzeteinek számát.

Beküldendő egy i463.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ó.

Letölthető állomány: nhalo.txt

(10 pont)

statisztika

I. 464. Közismert a kincsgyűjtögető játék, amelyben egy téglalap alakú tábla egyes mezőin haladva az érintett mezőkön elhelyezett kincseket megszerezhetjük. Továbblépni csak jobbra vagy lefele lehet. A cél az összességében a lehető legnagyobb értéket adó kincs begyűjtése.

A feladatot most táblázatkezelő program segítségével kell megoldanunk. A munkafüzet térkép munkalapján 16 sorban és 16 oszlopban helyeztünk el ,,kincseket'', pontosabban az azokat jelképező pozitív számokat.

Feladatunk, hogy feltételes formázás segítségével a térképre ,,rajzoljuk'' – az alábbi mintához hasonlóan – a legnagyobb összértékű kincs begyűjtését eredményező útvonalat. A térkép alatt jelenítsük meg az elérhető legmagasabb összértéket is.

A segédszámításokhoz tetszőleges számú munkalapot és cellát használhatunk. A megoldáshoz csak beépített függvények használhatók. A megoldás során törekedjünk másolható képletek használatára. (A felhasznált cellák és képletek száma a megoldás értékelését nem befolyásolja.)

Értékelés: a feladat hibamentes megoldásáért 7 pont kapható. A körültekintően elkészített, minden képlet szerepét megvilágító dokumentáció 3 pontot ér.

Beküldendő egy i464.zip tömörített állományban a megoldást tartalmazó i464 munkafüzet és a dokumentációt magában foglaló i464.pdf fájl. A dokumentáció tartalmazza a használt táblázatkezelő nevét, verziószámát és a megoldás során használt képleteket és azok szerepének leírását (a másolhatókat természetesen egyszer).

Letölthető állomány: kincs.txt

(10 pont)

megoldás, statisztika

I. 465. Adott egy \(\displaystyle R\) sugarú kör alakú lap (\(\displaystyle 10~\mathrm{mm} \le R \le 100~\mathrm{mm}\)), amelyet leteszünk a földre. A lapra \(\displaystyle N\) darab (\(\displaystyle 1 \le N \le 100\)) kisebb körlapot ejtünk véletlenszerűen úgy, hogy csak azokat az ejtéseket fogadjuk el, amelyeknél az ejtett lap nem lóg ki a földön lévő lapról. Az ejtett lapok átfedhetik egymást, de teljes egészében a lefektetett nagyobb lapon vannak. Kérdés, hogy a nagy lap területének hány százaléka nincs az \(\displaystyle N\) darab kisebb körlappal lefedve. Készítsünk szimulációs programot, amely modellezi a jelenséget, és minél pontosabban válaszol a kérdésre.

A program a standard bemenet első sorából olvassa be \(\displaystyle R\) és \(\displaystyle N\) értékét (egészek), valamint a következő sorból a leejtett körlapok sugarát (mindegyik sugár 1 mm-nél nagyobb, de \(\displaystyle R\)-nél kisebb egész érték). A standard kimenetre írjuk ki a lefektetett körlap nem lefedett részének területét négyzetmilliméter pontossággal.

Beküldendő egy i465.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/S-jelű feladatok A beküldési határidő 2018. november 12-én LEJÁRT.

I/S. 29. Egy ország városait kétirányú utak kötik össze, melyek használatáért díjat kell fizetni. Bármelyik városból bármelyik városba el lehet jutni az utakon. Két város között legfeljebb egy közvetlen út van. Néhány városban szupermarket is található. Az országba \(\displaystyle Q\) család érkezik, akik különböző vagyoni helyzetűek. Minden család szeretne olyan városba költözni, ahol nincs szupermarket. Ha egy család vagyoni helyzete \(\displaystyle K\), akkor csak olyan városban lakhat, ahonnan el tud menni bevásárolni egy szupermarketbe összesen legfeljebb \(\displaystyle K\) útdíjat fizetve (az oda- és visszautat számolva). Adjuk meg minden családra, hogy hány olyan város van az országban, ahol nincs szupermarket, mégsem tud odaköltözni a család, mert túl költséges lenne egy szupermarketbe való eljutás a vagyoni helyzetükhöz képest.

Bemenet: Az első sor tartalmazza a városok \(\displaystyle N\) számát, az utak \(\displaystyle M\) számát, a szupermarketet tartalmazó városok \(\displaystyle D\) számát és a családok \(\displaystyle Q\) számát. A következő \(\displaystyle M\) sor mindegyike három számot tartalmaz: az első kettő azon városok indexe, amik között az adott út van, a harmadik szám pedig az út használatának díja. A következő sorban \(\displaystyle D\) szám van: azon városok indexei, amikben van szupermarket. A következő sorban \(\displaystyle Q\) szám van: az \(\displaystyle i\)-edik szám az \(\displaystyle i\)-edik család vagyoni helyzetét leíró \(\displaystyle K\) érték. A városokat 0-tól \(\displaystyle N-1\)-ig indexeljük.

Kimenet: Egy sorba írjunk ki \(\displaystyle Q\) darab számot: a sor \(\displaystyle i\)-edik száma adja meg, hogy az \(\displaystyle i\)-edik család hány olyan városba nem tud költözni a vagyoni helyzete miatt, ahol nincs szupermarket.

Korlátok: \(\displaystyle 1\le D<N\le {10}^{5}\), \(\displaystyle 1\le M\le 5\cdot {10}^{5}\), \(\displaystyle 1\le Q\le {10}^{5}\), \(\displaystyle 0\le \text{egy}\) út díja, \(\displaystyle K\le 2\cdot 10^{9}\), egészek. Időkorlát: 0,5 s, memórialimit 100 MiB.

Értékelés: a pontok 20%-a kapható, ha minden út díja 1; további 20% kapható, ha \(\displaystyle D=1\); további 20% kapható, ha \(\displaystyle Q=1\); további 40% kapható az eredeti korlátokra.

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. november 12-én LEJÁRT.

S. 128. A fáraó elrendelte egy piramis építését, ehhez kőtömböket kell szállítani a bányától \(\displaystyle Q\) kilométerre levő építési területig. \(\displaystyle N\) kereskedő megadta, hogy mettől-meddig tud tömböt szállítani. Minden kereskedő legfeljebb egyszer szállít legfeljebb egy kőtömböt. A fáraó legfeljebb \(\displaystyle M\) kereskedőt kérhet meg a szállításra a költségek csökkentése érdekében. Segítsünk a fáraónak kiszámolni, hogy legfeljebb hány kőtömböt tud elszállíttatni az építési területre, és ehhez minimum hány embert kell megfizetnie. Egy kereskedő akkor tudja átadni a kőtömbjét egy másiknak szállításra, ha legalább addig el tudja vinni a tömböt, ahonnan a másik indulhat.

Bemenet: Az első sor tartalmazza a kereskedők \(\displaystyle N\) számát, a maximálisan megkérhető kereskedők \(\displaystyle M\) számát, valamint a bánya és az építési terület \(\displaystyle Q\) távolságát. A kereskedőket 0-tól \(\displaystyle N-1\)-ig sorszámozzuk. A következő \(\displaystyle N\) sor mindegyike két számot tartalmaz: az adott kereskedő hányadik kilométertől hányadik kilométerig tud szállítani.

Kimenet: Az első sorba írjuk ki, hogy maximum hány kőtömböt lehet elszállítani; a következő sorba, hogy ehhez minimálisan hány kereskedőnek kell fizetni.

Korlátok: \(\displaystyle 1\le M\le N\le {10}^{5}\), \(\displaystyle 0\le Q\le 2\cdot {10}^{9}\), egészek. Időlimit: 1 s, memórialimit 100 MiB.

Értékelés: A pontok 20%-a kapható, ha maximum egy tömböt tud a fáraó elszállíttatni; további 20% kapható, ha \(\displaystyle M=N\); további 20% kapható, ha \(\displaystyle N\le 1000\); további 10% kapható, ha \(\displaystyle Q\le {10}^{5}\); további 30% kapható az eredeti korlátokra.

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