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. januári 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. február 10-én LEJÁRT.


I. 418. (É). A KML-2017 expedíció elsőként érkezett meg egy égitestre, hogy megállapítsa annak kéreghez közeli szerkezetét. Egy vizsgálat során a felszínen egy irányban haladva 500 méterenként megmérték a felszín alatti rétegek vastagságát. A műszer által detektált értékek megtalálhatók a retegek.txt állományban. A szöveges fájl első sorában a mérések száma (\(\displaystyle 2\le M\le 200\)), valamint a műszer által mért rétegek száma (\(\displaystyle 1\le R\le 20\)) szerepel. A további \(\displaystyle R\) sor mindegyikében \(\displaystyle M\) darab nemnegatív egész mutatja az egyes rétegek \(\displaystyle V_\text{mr}\) vastagságát (\(\displaystyle 0 \le V_\text{mr} \le 10\,000\)) méterben. A rétegek a felszíntől lefelé haladva vannak fölsorolva, a vastagság zérus értéke azt jelenti, hogy azon a mérési helyen az adott réteg teljesen elvékonyodott. Példaként vizsgáljuk meg a következő bemeneti állományt (a rövidebb írásmód kedvéért három sortörést / jellel helyettesítettünk), valamint a mérési eredmények alapján a felszín alatti rétegek egy lehetséges rajzát, ahol a mért értékeket szakaszokkal kötöttük össze.

Készítsünk programot i418 néven, amely megoldja az alábbi feladatokat. A képernyőre írást igénylő részfeladatok eredményének megjelenítése előtt írjuk ki a feladat sorszámát (például 4. feladat:). A beolvasás előtt a várt tartalomra vonatkozó üzenetet jelenítsünk meg. Az ékezet nélküli kiírás is megengedett.

1. Olvassuk be és tároljuk a mérési eredményeket. Írjuk ki, hogy milyen hosszú úton végezte a csapat a mérést, illetve hány réteget rögzített a műszer.

2. Kérjük be egy réteg sorszámát, és adjuk meg, hogy az adott réteg hol és mekkora értékkel volt a legvastagabb és a legvékonyabb (pl. ,,A(z) 4. mérésnél volt a legvastagabb (3876 méter), és a(z) 1. mérésnél volt a legvékonyabb (2270 m) a(z) 4. réteg.'').

3. Állapítsuk meg, hogy hány réteg volt, amely a mérés során valahol teljesen elvékonyodott, és az eredményt írjuk ki (pl. ,,1 réteg vékonyodott el teljesen.'' vagy ,,Nem volt teljesen elvékonyodott réteg.'').

4. Számítsuk ki, hogy melyik mérési helyen, és a felszíntől milyen távol van a felszíntől legtávolabbi réteghatár (pl. ,,A(z) 7. mérési helyen 12723 méter mélyen van a legmélyebb feltérképezett réteghatár.'').

5. Kérjünk be egy mélység értéket (nemnegatív egész), és adjuk meg, hogy az egyes mérési pontokon a felszíntől számított hányadik rétegben van az adott mélység. Ha a távolság olyan nagy, hogy a mért rétegek alatt van, akkor a szám helyett egy kivonásjel kerüljön kiírása (pl. 9000 méterrel a felszín alatt az eredmény: 3 4 4 4 4 3 3).

6. Számoljuk meg, és írjuk ki, hogy hány olyan réteg van, amely a felszín valamely pontján is megjelenik (tehát az adott mérési helyen a felette lévő összes réteg vastagsága 0).

7. Előfordul, hogy egy réteg többször is eltűnik, de nem egymást követő mérési pontokon. Ilyenkor az adott rétegben ,,lencse'' alakul ki, amely el van zárva a saját rétege többi részétől. A felszínen nincsenek lencsék, tehát egy lencse minden pontja fölött kell lennie nem 0 vastagságú rétegnek. Keressük meg az ilyen lencséket, és írjuk ki mindegyik esetében, hogy hányadik rétegben található (azaz a lencse rétegének sorszámát), és legföljebb mekkora a hossza méterben mérve.

8. A mérési helyek között nem ismerjük a rétegek vastagságát és határvonaluk alakját, ezért két mérési hely között a rétegek határvonalát szakaszokkal helyettesítjük (ahogy a fenti ábrán). Ilyen módon minden réteg határvonala a kiindulási helytől számított bármely pontban megadható (a mérési helyeken pontosan, közöttük pedig a leírt közelítéssel). Számítsuk ki ezek alapján a kiindulási helytől számítva 100 méterenként, hogy az egyes rétegek középvonala a felszíntől mérve milyen mélységben halad. A réteg középvonala az adott helyen a felső és alsó határvonal számítani közepe. Az egész értékre kerekített értékeket a kozep.txt szöveges állományba írjuk ki. A fájl első sorában az indulási helytől mért távolságok szerepeljenek, majd a következő sorokban a rétegek középvonalai az adott helyen. Minden számérték között egy pontosvessző legyen a határoló jel.

Beküldendő egy tömörített i418.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ő szöveges állományok:

retegek.txt, retegek2.txt, retegek3.txt.

(10 pont)

megoldás, statisztika


I. 419. Számoljunk el különböző alapú számrendszerekben \(\displaystyle N\) (\(\displaystyle 1\le N\le 10)\) és \(\displaystyle N+19\) között egyesével. Az eredmények az alábbi táblázatban láthatók.

Állítsuk be, hogy a felhasználó csak az A2 cellába írhatja be \(\displaystyle N\) értékét, más cella tartalmát nem módosíthatja, de megtekintheti.

Segédszámításokat végezhetünk, amelyek értelmezését feliratokkal/megjegyzé­sekkel könnyítsük meg. A megoldásban saját függvény vagy makró nem használható.

Beküldendő egy i419.zip tömörített állományban a táblázatkezelő munkafüzet, illetve egy rövid dokumentáció, amelyben szerepel a megoldáskor alkalmazott táblázatkezelő neve és verziója.

(10 pont)

megoldás, statisztika


I. 420. A közlekedési járművekben sokféle navigációs eszközt használnak. A megtervezett és kiválasztott útvonal követését hangalámondással segítik. Az elhangzó utasításokat, figyelmeztetések kifejezéseit – kellemes hangú emberek hangján – az eszközben egy adatbázisban tárolják. A tájékoztató szöveget folyamatosan a navigációs szoftver állítja össze a fenti részletekből a jármű GPS koordinátái, a jármű menetjellemzői és a térkép ismeretében. A honlapunkról letölthető hangok.zip állomány ogg formátumban tartalmaz egy ilyen gyűjteményt.

Állítsunk össze egy hangállományt, amely azokat a navigációs utasításokat tartalmazza, amellyel a KöMaL szerkesztőségéből az MTA székházába lehet eljutni. Az útvonalat valamely ingyenes online útvonaltervezővel készítsük el. Az elhangzó utasítások sorozata segítse elő a megtervezett útvonalon való közlekedést. (Így ez egy vezérlési feladat, hiszen interakciót nem tartalmaz.) A feladat megoldásához használhatjuk például az Audacity ingyenesen elérhető programot.

Beküldendő egy tömörített i420.zip mappában az útvonalat bemutató képállomány és a hangfelvétel, illetve egy rövid dokumentáció, amelyben szerepel a megoldás menete.

Az összeállításhoz szükséges letölthető hangelemeket a hangok.zip fájl tartalmazza.

(10 pont)

megoldás, statisztika


I/S-jelű feladatok

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


I/S. 14. Meseországban rövid kirándulást teszünk, ahol az úthálózat nagyon egyszerű: az \(\displaystyle N\) érdekes helyszín mind egyetlen kör alakú út mentén helyezkedik el sorban. Kaptunk egy varázstérképet, amiről rögtön tudjuk, hogy melyik helyszín mennyire érdekes. A kirándulást bármelyik helyszínen elkezdhetjük, és bárhol befejezhetjük, viszont csak \(\displaystyle M\) percünk van. A térképről tudjuk bármely két szomszédos helyszínről, hogy mennyi ideig tart az út (az \(\displaystyle i\)-edik és az \(\displaystyle (i+1)\)-edik helyszín között \(\displaystyle U[i]\) percig (pozitív egész), az \(\displaystyle N\)-edik és az első helyszín között pedig az út \(\displaystyle U[N]\) percig tart).

Írjunk programot, amely a térkép alapján megtervez egy maximális érdekességű kirándulást (az érdekesség a meglátogatott helyszínek érdekességének összege; minden helyszín legfeljebb egyszer számít), és amely maximum \(\displaystyle M\) percig tart. (A helyszínek megtekintésének idejét nem vesszük figyelembe.)

A standard bemenet első sora tartalmazza a helyszínek \(\displaystyle N\) számát és a percek \(\displaystyle M\) számát (egész számok). A második sor \(\displaystyle N\) egész számot tartalmaz, az \(\displaystyle i\)-edik szám \(\displaystyle E[i]\) értéke az \(\displaystyle i\)-edik helyszín érdekessége. A harmadik sor \(\displaystyle N\) számot tartalmaz, az \(\displaystyle i\)-edik szám \(\displaystyle U[i]\) értéke. A standard kimenet első és egyetlen sorába írjuk ki a legérdekesebb út érdekességét.

Pontozás: Az első két tesztesetben \(\displaystyle N\le 100\). További két tesztesetben \(\displaystyle N\le 10\,000\).

Korlátok: \(\displaystyle 1\le N\le 10^6\), \(\displaystyle 1\le M,E[i],U[i]\le 10^9\).

Magyarázat: a második helyszínről indulva a harmadik helyszínen át a negyedik helyszínen befejezve \(\displaystyle 10+15+12=37\) az érdekességek összege, az idő pedig \(\displaystyle 10+20=30\), ami belefér a rendelkezésre álló 30 percbe.

(10 pont)

statisztika


S-jelű feladatok

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


S. 113. Egy állatkertben egy hosszú, egyirányú sétálóutca egyik oldalán található sorban mind az \(\displaystyle N\) állat kifutója. Az állatkert a világon előforduló összes állatfajt egy 1 és \(\displaystyle 10^9\) közötti egyedi (egész) számmal azonosítja. Tudjuk, hogy sorban az \(\displaystyle N\) kifutó közül melyikben milyen állat van. Az állatkert speciális túrákat tart. Minden túra résztvevői két tetszőleges kifutó között megtekinthetik az összes állatot. A túra során elengedhetetlen, hogy a látogatók minden, az állatkertben megtalálható állatfajnak legalább egy egyedét láthassák. Az állatkert vezetése kíváncsi, hogy hányféle különböző túrát lehet az állatkertben vezetni ennek a feltételnek a betartásával. Két túra különböző, ha a kezdőpontjuk vagy a végpontjuk különböző. A sétálóutca egyirányú, tehát a résztvevők nem sétálhatnak visszafelé. Készítsünk programot, amely megadja a feltételnek eleget tevő túrák számát.

A standard bemenet első sorában a kifutók \(\displaystyle N\) száma van, a következő sor tartalmazza a kifutók ,,lakóinak'' azonosítóját sorrendben.

A standard kimenet egyetlen egész számot tartalmazzon: a különböző túrák számát.

Pontozás: Az első két tesztesetben \(\displaystyle N\le 100\), a harmadik tesztesetben \(\displaystyle N\le 5000\).

Korlátok: \(\displaystyle 1\le N\le 2\cdot 10^5\), minden állatfaj azonosítója 1 és \(\displaystyle 10^9\) közötti egész, az időkorlát 1 mp.

Magyarázat: a helyes túrák (kezdőponttal és végponttal megadva): (1,3), (1,4), (1,5), (1,6), (2,5), (2,6), (3,5), (3,6), (4,6).

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