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 2019. májusi 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ő 2019. június 11-én LEJÁRT.


I. 484. A Hanoi tornyai nevű játék rendkívül egyszerű. Három rúddal és \(\displaystyle N\) darab különböző méretű koronggal játszható. Kezdetben az egyik rúdon \(\displaystyle N\) korong helyezkedik el, alul a legnagyobb, majd fölötte rendre a kisebbek. Ekkor a másik két rúd üres. A játék szabályai szerint az egyik rúdról egy másikra kell átrakni a korongokat úgy, hogy minden lépésben egy korongot lehet áttenni, de nagyobb korong nem tehető kisebb korongra.

Peti is elkezdte játszani a játékot, de nem ért a végére. A játékot egy ilyen állapotban találjuk meg. Készítsünk programot, amely megad egy lehetséges lépéssorozatot, amellyel ez az állapot előállítható.

A program standard bemenetének első sorában annak a rúdnak a sorszáma szerepel, amelyen kezdetben az összes korong volt. A következő sorban három szám, az egyes rudakon található korongok száma van. A következő három sorban az adott rúdon található korongok mérete szerepel csökkenő sorrendben. A kimenet első sora egyetlen számot tartalmaz, az állapot eléréséhez szükséges lépések L számát. A következő \(\displaystyle L\) sor mindegyikében két szám található, egymástól pontosan egy szóközzel elválasztva. Az első szám megadja a rudat amelyről, a második pedig azt a rudat, amelyre átkerül a felső korong. Feltételezhetjük, hogy Peti legfeljebb 10 koronggal játszik.

Beküldendő egy i484.zip tömörített állományban a program forráskódja és a hozzá kapcsolódó dokumentáció. Utóbbi a problémamegoldás lényeges elemeire világít rá, valamint tartalmazza, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

megoldás, statisztika


I. 485. Magyarország nagyobb közúti, vasúti, jelentősebb gyalogos és kerékpáros hídjainak, völgyhídjainak adatai állnak rendelkezésünkre a hidak.txt, kapcsolo.txt, funkcio.txt, hely.txt és a telepules.txt állományokban. 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 i485 néven. A mellékelt adatállományokat importáljuk az adatbázisba a forrásállományokkal azonos néven. Vegyük figyelembe, hogy több hídnak nem minden adata ismert.

2. Beolvasáskor állítsuk be a megfelelő adattípusokat és kulcsokat. A táblákba ne vegyünk fel új mezőt.

észítsük el a következő feladatok megoldását. 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.

3. A tervezett, vagy épülőben lévő hidak átadási éve nem ismert. Soroljuk fel ezeknek a hidaknak a nevét, hosszát és adjuk meg, hogy mit ívelnek át. (3uj)

4. Ritkának gondolhatjuk a kerékpáros és gyalogos hidakat. Lekérdezés segítségével soroljuk fel ezeknek a hidaknak a nevét, hosszát, funkcióját és korát a mai dátumhoz képest. A lista a kor szerint csökkenően jelenjen meg. (4ritka)

5. A hidak nem feltétlenül településen belül vannak, hanem többet össze is köthetnek. Lekérdezéssel határozzuk meg ezeket a hidakat az összekötött települések nevével együtt. (5osszekot)

6. Adjuk meg megyénként az adatbázisban szereplő hidak számát. Ha egy híd különböző megyében lévő településeket köt össze, többször számolhatjuk. A lista a hidak száma szerint csökkenően jelenjen meg. (6megyenkent)

7. Határozzuk meg azoknak a hidaknak a nevét, amelyeknek ,,közúti'' és ,,vasúti'' funkciója is van egyszerre. A listában minden hídnév egyszer jelenjen meg. (7tobbfunkcios)

8. A települések nevét nem mindig tudjuk pontosan. Paraméteres lekérdezés segítségével adjuk meg egy településnév részletéhez az illeszkedő településeket és településeken lévő hidak nevét. (8reszlet)

9. Határozzuk meg lekérdezés segítségével az oszlopok sorrendjétől eltekintve a minta szerint, hogy Budapesten melyik hídtípusból hány darab van. A többfunkciósokat mindegyikhez számoljuk be. (9osszesites)

Beküldendő egy tömörített i485.zip állományban az adatbázis, valamint egy rövid dokumentáció, amely megadja az alkalmazott adatbázis-kezelő nevét és verziószámát.

Letölthető fájlok: hidak.txt, kapcsolo.txt, funkcio.txt, hely.txt, telepules.txt.

(10 pont)

megoldás, statisztika


I. 486. Monte Carlo városában két egyenrangú út keresztezi egymást. A város vezetése azon gondolkodik, hogy a kereszteződést körforgalommá építse át. Az átépítést abban az esetben végeznék el, ha az autók átlagos áthaladási ideje a körforgalomban kisebb lenne, mint a kereszteződésben. Készítsünk programot, amely adott közlekedési viszonyok mellett megadja a kereszteződés és a körforgalom esetén az átlagos áthaladási időt!

A város autósai különösen udvarias emberek, akik a következő szabályok betartásával közlekednek:

1. a kereszteződésben, illetve a körfogalomban mindig az érkezés sorrendjében történik az áthaladás;

2. ha több autó egyszerre érkezik, akkor az kezdheti meg az áthaladást, akinek az a legkevesebb ideig tart; ha több ilyen jármű is van, akkor a jobbkéz-szabály alapján kezdik meg az áthaladást; ha mindegyik jármű ilyen, akkor véletlenszerűen választanak egyet, és ő kezdi meg az áthaladást, majd azután alkalmazzák a jobbkéz-szabályt;

3. két autó egyszerre is beléphet a kereszteződésbe abban az esetben, ha útjuk nem keresztezi egymást;

4. a körforgalomban haladó járműnek elsőbbsége van az oda belépni akaró járműhöz képest.

A feladatban tekintsünk minden autót egyforma hosszúságúnak, valamint feltételezzük, hogy azonos sebességgel haladnak. Mozgásukat úgy értelmezzük, hogy egységnyi idő alatt az ábrán látható négyzetháló egy cellájából a haladásnak megfelelő, oldalával szomszédos cellába lépnek át, ha az a cella üres (vagyis nem áll ott autó, vagy az ott álló autó tovább tud lépni a cellába belépő autóval egy időben).

A kereszteződés és a körforgalom négyzethálós felbontása az ábra szerint történjen. A példában a négy csatlakozó útszakaszt az óramutató járása szerint az 1, 2, 3, 4 számok, az autókat kétjegyű számok jelölik: a tízesek helyén annak az útszakasznak a sorszáma van, ahonnan érkezik, az egyesek helyén ahová tart az autó.

A szimulációs programban az útszakaszok \(\displaystyle L\) hosszúak legyenek, tehát egy útszakaszon sávonként \(\displaystyle L\) négyzet csatlakozzon a kereszteződéshez, illetve a körforgalomhoz. Minden esetben összesen \(\displaystyle N\) számú autóval induljon a szimuláció, melyek mindegyike a kereszteződés, illetve a körforgalom felé tart. Az autók egyike sem fordul vissza, tehát mindegyik egy másik útszakaszon halad tovább. A program adja meg, hogy \(\displaystyle S\) számú szimuláció esetén mennyi az átlagos áthaladási idő. Ez az idő egyenlő egy-egy autó esetén a kereszteződés vagy körforgalom miatti várakozás és áthaladás idejével, tehát attól az időegységtől kezdődik, amikor az autó várakozni kényszerül a bevezető úton, vagy várakozás nélkül belép a kereszteződésbe, illetve körforgalomba, és akkor ér véget, amikor onnan kilép. Így egy 1-es útszakaszról a 4-es útszakaszba tartó, jobbra kanyarodó autó a kereszteződés esetén legkevesebb 2, a körforgalom esetén legkevesebb 4 időegység alatt halad át.

A program a standard bemenetről olvassa be \(\displaystyle L\), \(\displaystyle N\) és \(\displaystyle S\) értékét, majd a standard kimenet egy sorába írja az átlagos áthaladási időket a kereszteződés és körforgalom esetén. Korlátok: \(\displaystyle 10\le L\le 100\), \(\displaystyle L\le N< 4L\), \(\displaystyle 100\le S\le 10000\).

Beküldendő egy i486.zip tömörített állományban a program forráskódja és a hozzá kapcsolódó dokumentáció. Utóbbi a problémamegoldás lényeges elemeire világít rá, valamint tartalmazza, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

megoldás, statisztika


I/S-jelű feladatok

A beküldési határidő 2019. június 11-én LEJÁRT.


I/S. 36. Hányféleképpen lehet felépíteni egy \(\displaystyle N\) egység magasságú \(\displaystyle 2\times 2\)-es alapú oszlopot, \(\displaystyle 1\times 1\times 2\) méretű téglatestekből? Ez a szám nagyon nagy is lehet, ezért az \(\displaystyle 1\,000\,000\,007\)-es maradékát adjuk meg.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) számot.

Kimenet: adjuk meg, hogy hányféleképpen tudjuk felépíteni az oszlopot. A forgatással egymásba vihető építéseket is különbözőnek tekintjük.

Korlátok: \(\displaystyle 1\le N\le {10}^{6}\).

Időlimit: 0,1 mp.

Bemenet Kimenet
3 32

Beküldendő egy is36.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.

(10 pont)

statisztika


S-jelű feladatok

A beküldési határidő 2019. június 11-én LEJÁRT.


S. 135. Adott egy terület domborzati térképe, amelyre gondolatban egy \(\displaystyle N\times N\)-es négyzethálót terítünk. A négyzetháló minden négyzetéhez hozzárendelünk a térkép alapján egy magasság értéket. Szeretnénk bejárni a terület felét, azaz a négyzetek legalább felét (páratlan \(\displaystyle N\) esetén felső egészrészt véve). A bejárás során egy-egy négyzetről csak egy vele oldalszomszédos négyzetre tudunk átmenni, ha a két négyzet magasság értékének különbsége legfeljebb \(\displaystyle D\). Adjuk meg azt a legkisebb \(\displaystyle D\) értéket, amivel be tudjuk járni a terület legalább felét, ha a bejárás tetszőleges négyzetről indulhat.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) számot; a következő \(\displaystyle N\) sor mindegyike \(\displaystyle N\) számot tartalmaz: az \(\displaystyle i\). sor \(\displaystyle j\). száma az \(\displaystyle i\). sor \(\displaystyle j\). négyzetének magasságértékét adja meg.

Kimenet: a legkisebb \(\displaystyle D\) egész szám, amivel megvalósítható a bejárás.

Korlátok: \(\displaystyle 1\le N\le 500\), \(\displaystyle 0\le \text{egy négyzet magassága}\le {10}^{6}\).

Időlimit: 0,3 mp.

Beküldendő egy s135.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztő környezetben futtatható.

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