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 2017. áprilisi 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ő 2017. május 10-én LEJÁRT.


I. 427. Adott \(\displaystyle 1 \le N \le 1\,000\) város. Minden városból legfeljebb egy egyirányú út vezethet egy másik városba. A bemenet pontosan \(\displaystyle N\) db számot tartalmaz: az \(\displaystyle i\)-edik szám annak az \(\displaystyle i\)-től különböző városnak a sorszáma, amelybe \(\displaystyle i\)-ből út vezet. Ha nincs ilyen út, akkor a szám 0. Bizonyos városokból elindulva akár végtelen sokáig is sétálhatunk az egyirányú utak mentén, a többi város esetén ez nem lehetséges. Számoljuk meg, hány olyan város van, amelyből véges lépésszámú út indul ki.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et, majd a következő \(\displaystyle N\) sorból rendre az adott városból közvetlenül elérhető másik város sorszámát. A program írja a standard output első sorába azon városok számát, amelyekből véges lépésszámú út indul ki, majd a következő sorba szóközzel elválasztva az ilyen városok sorszámát.

Példa bemenet (a / jel újsort jelöl):Példa kimenet:
5 / 0 / 4 / 1 / 5 / 42 / 1 3

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

Javasolta: Weisz Ágoston (Budapest)

(10 pont)

statisztika


I. 428. (É). A kerti munkákat gondosan kell ütemezni, ha sokféle gyümölcsfánk van. Foglaljuk adatbázisba a kert gyümölcsfáinak és az elvégzendő munkákra fajonként ajánlott időszakok adatait. Az adatok a gyumolcs.txt, a muvelet.txt és az idoszak.txt állományokban állnak rendelkezésünkre. Az állományok tabulátorral tagolt, UTF-8 kódolású szövegfájlok, az első sorok a mezőneveket tartalmazzák.

1. Készítsünk új adatbázist i428 néven. A mellékelt adatállományokat importáljuk az adatbázisba a fájlnévvel azonos nevű táblákba. Beolvasáskor állítsuk be a megfelelő adatformátumokat és kulcsokat. A muvelet táblához adjunk hozzá az néven egyedi azonosítót.

Táblák

Készítsük el a következő feladatok megoldásait. Az egyes lekérdezéseknél ügyeljünk arra, hogy mindig csak a kért értékek jelenjenek meg és más adatok viszont ne. A megoldásainkat a zárójelben lévő néven mentsük el. Ha szükséges, készítsünk honap néven táblát a hónapok sorszámának tárolására.

2. Készítsünk lekérdezést, amely ábécérendben jeleníti meg a gyümölcsfa fajok nevét és a rajtuk végzendő kerti munkákat. Gondoskodjunk arról, hogy a listában ismétlődés ne legyen. (2feladatlista)

3. Soroljuk fel lekérdezés segítségével a fák ültetésére megadott hónapok nevét. Például: március. (3ultetes)

4. Készítsünk lekérdezést, amely meghatározza, hogy melyik az a kerti munka, amelyhez a leghosszabb egybefüggő időszak van megadva. (4leghosszabb)

5. Zöldmetszésnek nevezik, amikor leveles ágakat, hajtásokat távolítanak el. Soroljuk fel lekérdezés segítségével azokat a fajokat, amelyeken zöldmetszés végezhető, azaz a metszés a 4. és 9. hó közé esik beleértve a határokat is. (5zoldmetszes)

6. Lekérdezés segítségével adjuk meg, hogy az adatbázisban nyilvántartott kertben, júliusban, hány fa szüretelésére kell felkészülni összesen. (6julius)

7. Lekérdezés segítségével soroljuk fel azokat a gyümölcsfajokat, amelyeknek a metszési időszaka pontosan megegyezik az almáéval. (7azonos)

8. A vegyszeres permetezéssel nagyon vigyázni kell, mert a szerek használata az egészségre is veszélyes. Adjuk meg hónap és gyümölcsfaj formában, hogy az adott gyümölcsfaj esetén melyik hónapban szabad utoljára növényvédő és gombaölő szeres permetezést alkalmazni szüretelés előtt. (8nopermetezes)

9. Adjuk meg lekérdezés segítségével azokat a hónapokat, amikor szüret és ültetés is végezhető a kertben. (9sokmunka)

10. Lekérdezés segítségével számoljuk meg, hogy a kert adatbázisában hány olyan gyümölcsfaj található, amelyek fáinak száma az 1–3, 4–6, 7–9 és 10–12 tartományokban van. (10mennyiseg)

Beküldendő egy tömörített i428.zip állományban az adatbázis, valamint egy rövid dokumentáció, amelyből kiderül az alkalmazott adatbázis-kezelő neve és verziószáma.

Letölthető állományok: a gyumolcs.txt, a muvelet.txt és az idoszak.txt.

(10 pont)

megoldás, statisztika


I. 429. Egy edényben, melynek felszíne téglalap alakú, folyadék található. A folyadék felszínén \(\displaystyle N\) helyen (\(\displaystyle 1 \le N \le 50\)) szigeteket hozunk létre, melyek mindegyikére azonos számú inaktív baktériumot telepítünk. Az összesen \(\displaystyle K\) számú (\(\displaystyle 100\le K \le 10\,000\)) baktériumból minden szigetre \(\displaystyle \lfloor K/N\rfloor\) kerül. Az edény oldalhossza \(\displaystyle a\) és \(\displaystyle b\) egység (\(\displaystyle 50 \le a~\le b \le 500\)). A folyadék felszínére gondolatban az oldalakkal párhuzamosan egy négyzethálót fektetünk. Az így keletkező \(\displaystyle a\cdot b\) darab egységnégyzet bármelyike pontosan egy szigetet, vagy a folyadék szabad felszínét fedi le. Mindkét fajta egységnégyzet tetszőleges számú baktériumot tartalmazhat. Az \(\displaystyle s\)-edik sziget (\(\displaystyle 1\le s \le N\)) négyzete az egyik hosszabb oldaltól \(\displaystyle \lfloor a/2\rfloor\) és az egyik rövidebb oldaltól \(\displaystyle \big\lfloor s\cdot b/(N+1)\big\rfloor\) távolságra van (tehát a szigetek a rövidebb oldal felezőmerőlegeséhez közel, az oldaltól és egymástól nagyjából egyenlő távolságban vannak).

A szigeteken lévő inaktív baktériumok korlátlan ideig a szigetükön maradnak. A folyadék belsejében elhelyezünk 0 életkorú aktív baktériumokat is, melyek legföljebb \(\displaystyle T\) ideig (\(\displaystyle 10 \le T\le 100\)) véletlenszerűen mozognak a folyadék felszínén, az edény belsejében, majd elpusztulnak. Ha egy aktív baktérium életének egy bizonyos időszakában ismét egy szigetre érkezik, ahol van inaktív baktérium, akkor az aktív és az egyik inaktív baktérium elpusztul, és kettőjük helyett összesen \(\displaystyle U\) számú (\(\displaystyle 4\le U\le 10\)) új, aktív baktérium jön létre.

A baktériumokat kutató tudósok nem tudják megállapítani, hogy egy edényben hány szigetet hozzanak létre, hogy az összes baktérium meghatározott időn belül aktiválódjon. Készítsünk szimulációs programot, amely modellezi a jelenséget, és megadja, hogy adott paraméterek mellett hány szigetet érdemes létrehozni. A szimuláció minden lépése egység ideig tartson, és a következők történjenek:

– minden aktív baktérium

\(\displaystyle \qquad\circ\) átlép az egységnégyzetével oldalszomszédos, véletlenszerűen választott négyzetbe és életkora eggyel nő;

\(\displaystyle \qquad\circ\) ha egy sziget négyzetébe ért, akkor

\(\displaystyle \qquad\qquad\bullet\) ha életkora \(\displaystyle 4T/10\) és \(\displaystyle 6T/10\) közötti, és a szigeten van inaktív baktérium, akkor az aktív és az egyik inaktív baktérium elpusztul, és helyettük \(\displaystyle U\) számú új, 0 életkorú aktív baktérium jön létre a sziget négyzetében;

\(\displaystyle \qquad\qquad\bullet\) ha életkora nem a fenti értékek között van, akkor nem történik semmi, a következő szimulációs periódusban folytatja bolyongását;

\(\displaystyle \qquad\circ\) ha a baktérium életkora nagyobb, mint \(\displaystyle T\), akkor elpusztul.

Az aktív baktériumok egymással történő találkozásakor nem történik semmi. A szimuláció kezdetekor elhelyezzük a szigeteket az inaktív baktériumokkal, és beteszünk az edénybe az egyik szélső szigetre 50 darab, 0 életkorú aktív baktériumot. A szimuláció legföljebb \(\displaystyle 10\,000\) időegységig tartson, vagy amíg van az edényben aktív baktérium.

A program olvassa be a standard input első sorából \(\displaystyle K\), \(\displaystyle U\), \(\displaystyle T\), \(\displaystyle a\) és \(\displaystyle b\) értékét, majd írja a standard output első sorába azon \(\displaystyle N\) értékeket, amelyeknél az összes baktérium aktiválódik. A szimulációt az adott paraméterekkel és minden lehetséges \(\displaystyle N\)-nel legalább 100-szor futtassuk le.

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

(10 pont)

megoldás, statisztika


I/S-jelű feladatok

A beküldési határidő 2017. május 10-én LEJÁRT.


I/S. 17. Julcsi és Marcsi egy szabályos dobókockával (a szemközti oldalakon levő pontok összege mindig 7) játszanak egy \(\displaystyle S\cdot O\) cellából álló négyzetrácson. A négyzetrács egy cellája pontosan akkora, mint a dobókocka egy oldallapja. A rács bal felső cellájára teszik le a dobókockát úgy, hogy az oldalai párhuzamosak a rács oldalaival, felfele az egyes szám, a tőle jobbra levő oldalon a hármas, a tőle lefele levő cella felé pedig a kettes néz.

Jobbra végiggörgetik a kockát a rácson, míg el nem éri az utolsó cellát, ekkor lefelé gördítik a következő sorba, majd balra vissza addig, míg el nem érik a bal oldalát a rácsnak. Itt újra lefelé gördítenek rajta egyet, s ezeket a lépéseket ismétlik mindaddig, míg az összes cellát be nem járta a kocka. Minden lépés után megnézik, hogy hányas szám van a kocka tetején, és az így megnézett számokat összeadják. Mennyi lesz az összeg?

A bemenet egyetlen sorában két pozitív egész szám áll, \(\displaystyle S\) és \(\displaystyle O\) (\(\displaystyle 1 \le S, O \le 100\,000\)), a négyzetrács sorainak és oszlopainak a száma. A kimenet első és egyetlen sora a kapott összeget tartalmazza.

Az első 4 tesztesetben (4 pontért) \(\displaystyle 1 \le S, O \le 100\).

Példa:

BemenetekKimenetek
3 219
3 442
737 296763532

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

Megjegyzés: Megoldható-e a feladat akkor is, ha nincs korlát \(\displaystyle S\)-re és \(\displaystyle O\)-ra, csak annyit tudunk, hogy a megoldás \(\displaystyle 10^{18}\)-nál kisebb?

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2017. május 10-én LEJÁRT.


S. 116. Egy ország úthálózata kétirányú, egyenes autópályákból áll, melyek egy-egy várospárt kötnek össze. Minden útnak ismerjük a két végpontját, illetve a megtételéhez szükséges időt. Az országban két város (A és B) gyors fejlődésnek indult, így az ország vezetői minimalizálni szeretnék a két város közötti út megtételének idejét. Sajnos földrajzi okokból nem tudnak újabb autópályákat építeni. Kifejlesztettek egy közlekedési eszközt, egyenes számára kiépített speciális pályán elhanyagolható idő alatt (0) juttatja el a rakományát, vagy utasait a pálya két végpontja között. Mivel ez az új jármű nagyon drága, csak egyetlen darabot tudnak belőle megépíteni. A jármű vonalát csak egy már meglévő autópályával párhuzamosan lehet kiépíteni.

Írjunk programot, ami segít az ország vezetőinek megmondani, hogy melyik két város közötti autópálya mellé építsék ki a kifejlesztett közlekedési eszköz vonalát, illetve megmondja, hogy mennyivel csökken az utazási idő A és B között. A városokat 1 és \(\displaystyle N\) közötti sorszámokkal azonosítjuk.

A standard bemenet első sora a városok \(\displaystyle N\) számát és az autópályák \(\displaystyle M\) számát, illetve \(\displaystyle A\) és \(\displaystyle B\) sorszámát tartalmazza. A következő \(\displaystyle M\) sor egy-egy autópályát ír le, vagyis három egész számot tartalmaz szóközzel elválasztva: a két végpont sorszámát \(\displaystyle (x_{i},y_{i})\), illetve az adott autópálya megtételéhez szükséges időt (\(\displaystyle z_{i}\)-t) tartalmazza. Az A városból a B városba mindenképp el lehet jutni egy vagy több autópályán végighaladva. A standard kimenet első sorába írjuk ki, hogy maximum mennyivel csökkenthető az utazási idő A és B között, a második sorba pedig annak a két városnak sorszámát, amelyek között az új vonalat építeni kell.

Bemenet (a / jel sortörést jelöl)Kimenet
5 7 1 2 / 1 3 2 / 1 4 4 / 3 4 3 / 3 2 10 / 4 2 20 / 2 5 1 / 5 4 25 / 3 2

Magyarázat: az ábráról látszik, hogy a 3-as és 2-es pont közé építve a vonalat az utazási idő 7-ről 2-re csökken.

Korlátok: \(\displaystyle 2 \le N \le 100\,000\), \(\displaystyle 1 \le M \le 1\,000\,000\), \(\displaystyle 1 \le A\ne B \le N\), \(\displaystyle 1 \le x_{i}\ne y_{i} \le N\), \(\displaystyle 0 \le z_{i} \le 10\,000\). Az időlimit 1 mp, a memórialimit 256 MB. Az első két tesztesetben az előbbi korlátokon kívül teljesül, hogy \(\displaystyle M \le 1000\).

Pontozás: a programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani a fenti korlátoknak megfelelően.

Beküldendő egy tömörített s116.zip állományban a program forráskódja (az .exe és más, a fordító által generált állományok nélkül), valamint a program rövid dokumentációja, amely leírja a megoldás menetét és megadja, hogy a forrás mely fejlesztői környezetben fordítható. Az utolsó két tesztesetre maximális pont csak akkor érhető el, ha a dokumentáció fent leírt bizonyítást tartalmazza.

(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.