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 2014. októberi 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ő 2014. november 10-én LEJÁRT.


I. 355. Egy városban \(\displaystyle M\) metróvonal és \(\displaystyle V\) villamosvonal található. Minden metróvonal és villamosvonal megállók rendezett sorozatából áll, ezek mentén lehet mindkét irányban közlekedni. Két vonal között akkor lehet átszállni, ha van azonos nevű megállójuk. Válaszoljunk a következő kérdésekre:

\(\displaystyle a)\) Adjuk meg, hány állomás van a városban.

\(\displaystyle b)\) Adjuk meg, hány megállóból áll a leghosszabb metró- és a leghosszabb villamosvonal.

\(\displaystyle c)\) Adjuk meg azokat a megállókat, melyek nem érhetőek el csak metró használatával.

\(\displaystyle d)\) Adjunk meg két állomást, amelyek a legtávolabb vannak egymástól, és adjuk meg, hogy mekkora ez a távolság. A távolságot most úgy értjük, hogy hány megállót kell megtenni a két állomás közötti legrövidebb úton.

\(\displaystyle e)\) Ha a lehető legkevesebb átszállással akarunk eljutni egy tetszőleges állomásról egy tetszőleges másikra, akkor mennyi az a legkevesebb átszállás, amit legrosszabb esetben mindenképp meg kell tennünk? Adjuk meg az átszállások számát és két olyan állomást, melyek közül az egyikből a másikba ennyi átszállásnál kevesebből nem lehet eljutni.

A program a standard bemenet első sorából olvassa be az \(\displaystyle M\) és \(\displaystyle V\) számokat (\(\displaystyle 1\le M,V\le 100\)), és a következő \(\displaystyle M\) sorból a metróvonalakat: minden sor elején egy egész szám van, a metróvonal megállóinak száma, majd utána a megállók nevei vesszőkkel és egy szóközzel elválasztva. Ezután a következő \(\displaystyle V\) sorban ugyanígy a villamosvonalak leírása található. A program írja ki a standard output első öt sorába a kérdésekre adott válaszokat.

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

(10 pont)

megoldás, statisztika


I. 356. A megyeszékhely fogorvosi rendelőjében minden munkanap három fogorvos várja a pácienseket. A rendelő szabott áron dolgozik. Az adatbázisban a 2011-es év adatait dolgoztuk fel. Az adatokat a könnyebb kezelhetőség érdekében a hivatalos módtól eltérően, egyszerűbben rögzítettük.

1. Készítsünk új adatbázist fogorvos néven. A mellékelt négy - tabulátorokkal tagolt, UTF-8 kódolású - szöveges állományt (paciens.txt, beavatkozas.txt, kategoria.txt, fizetendo.txt) importáljuk az adatbázisba a fájlnévvel azonos néven ( paciens, beavatkozas, kategoria, fizetendo). Az állomány első sora a mezőneveket tartalmazza. A létrehozás során állítsuk be a megfelelő típusokat és kulcsokat.

Táblák:

A következő feladatok megoldásánál a lekérdezéseket a zárójelben olvasható néven mentse. Ügyeljen arra, hogy a megoldásban pontosan a kívánt mezők szerepeljenek.

2. Készítsünk lekérdezést, amely megadja, hogy az árlistában melyik beavatkozás a legdrágább. (2legdragabb)

3. A 2011-es évben többször volt munkanap áthelyezés, ami azt jelenti, hogy egy munkanap helyett szombaton kellett dolgozni. Ez történt a rendelőben is. Készítsünk lekérdezést, amely megadja azokat a szombatokat, amelyen dolgozni kellett. (3szombat)

4. Készítsünk lekérdezést, amely megadja, hogy az egyes orvosoknak mekkora bevétele volt 2011-ben. (4bevetel)

5. Készítsünk lekérdezést, amely megadja, hogy a bölcsességfogat érintő beavatkozásnak hány százaléka eltávolítás. (5eltavolitas)

6. Készítsünk lekérdezést, amely megadja, hogy az 1111-es azonosítójú páciens kikkel nem találkozhatott a rendelőben. (6nemtalalkozott)

7. Készítsünk lekérdezést, amely megadja, hogy az első vagy a második kisőrlő fogat kell-e gyakrabban kezelni. A lekérdezéssel csak a fog nevét jelenítsük meg. Feltételezhetjük, hogy a kérdés egyértelműen eldönthető. (7kisorlo)

8. Készítsünk lekérdezést, amely megadja azon páciensek azonosítóját, akik három héten, azaz 21 napon belül háromszor is felkeresték a rendelőt. (8harom)

9. Készítsünk lekérdezést, amely megadja azokat, akiknek két egymás melletti fogát is kezelték 2011-ben. (9szomszedos)

Beküldendő egy tömörített állományban (i356.zip) a megoldást tartalmazó adatbázis vagy az SQL lekérdezéseket tartalmazó szövegfájl (fogorvos.odb, fogorvos.mdb, fogorvos.sql), valamint egy rövid dokumentáció (i356.txt, i356.pdf), amelyből kiderül az alkalmazott adatbázis-kezelő neve és verziószáma.

Letöltendő fájlok:

beavatkozas.txt

fizetendo.txt

kategoria.txt

paciens.txt

(10 pont)

megoldás, statisztika


I. 357. Moarénak nevezik az óriásplakátokon, a digitális fényképeken, a vonalas és a szabályos mintájú ábrákon megjelenő nem várt mintázatokat. A fotósok munkáját ez időnként megnehezíti. A jelenség a szabályos alakzatokon kialakuló interferencia eredménye. A finom szálakból felépülő textíliákon és a szép hosszú, egyenes szálú hajon is kialakulhat moaré. A geometrikus, ismétlődő részleteket tartalmazó tárgyakon, például kerítéseken, rácsokon, a határozott függőleges vonalak gyakran vezetnek moaré kialakulásához.

Készítsünk animációt egy SVG típusú vektorgrafikus képállományba, amely egy egyszerű moaré kialakulását mutatja be.

A böngészők (kivétel az Internet Explorer) az SVG állományt képesek megfelelően megjeleníteni. Az SVG állomány és abban az animáció szerkezetéről a http://svg.elte.hu/ címen olvashatunk. A megoldáshoz ajánljuk az Inkscape nevű (internetről ingyenesen letölthető) vektorgrafikus rajzolóprogramot.

Az animáción szereplő alakzatokat, legegyszerűbb esetben csíkos kitöltésű négyzeteket vagy ponthálót, de más vonalas ábrákat is, érdemes a vektorgrafikus rajzolóprogrammal elkészíteni. Az animációt a képállomány szövegének szerkesztésével oldjuk meg.

Az animáción az alakzatok egymás fölött mozogjanak (forgás vagy transzláció, ...) olyan sebességgel, hogy a moaré kialakulása megfigyelhető legyen. A lejátszási idő, ismétlődések száma valamint más paraméterek szabadon választhatók.

Beküldendő a képállomány (i357.svg), valamint egy rövid leírás (i357.txt, i357.pdf, ...), amely tartalmazza a kód animációt megvalósító részének elemzését.

(10 pont)

megoldás, statisztika


S-jelű feladatok

A beküldési határidő 2014. november 10-én LEJÁRT.


S. 92. Adott \(\displaystyle N\) (\(\displaystyle 1\le N\le 2\;000\;000\)) db nem feltétlenül különböző egész számunk egy sorozatban, melyek mindegyike 1 és 1000000000 között van. Válasszunk ki adott \(\displaystyle K\) számú (\(\displaystyle 1\le K\le N\)) különböző egészet a sorozatból úgy, hogy törölve a kiválasztott számokat és azok összes többi előfordulását, a lehető leghosszabb azonos számokból álló összefüggő részsorozat szerepeljen a megmaradt számokat tartalmazó sorozatban.

A program olvassa be a standard input első sorából \(\displaystyle N\)-et és \(\displaystyle K\)-t, majd a következő sorból a sorozat tagjait, majd írja a standard output első sorába a leghosszabb elérhető részsorozat hosszát.

Magyarázat a példához: ha töröljük az összes 3-ast a sorozatból, akkor a következőt kapjuk: 2 7 7 7 7 5 7, itt nyilván 4 db egymás utáni 7-es a leghosszabb. Ha más számot törölnénk, akkor sem fordulna elő ennél hosszabb azonos számokból álló összefüggő részsorozat a visszamaradt sorozatban.

Pontozás és korlátok: 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 az 1 mp futásidőkorláton belül.

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

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