A KöMaL 2014. 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ű feladatokA beküldési határidő 2014. június 10-én LEJÁRT. |
I. 349. Egy \(\displaystyle N\times M\) (\(\displaystyle 2\le N,M\le 50\)) négyzet alakú és egyforma méretű telkekből álló lakótelepen a házak magassága, szintjeinek száma \(\displaystyle K\) (\(\displaystyle 1\le K\le 9\)). Az épületek minden szintjén egy lakás található. A 0 érték parkot jelöl. Szomszéd négyzeteken most négyet értünk, az ábrának megfelelően.
Készítsünk programot i349 néven, amely a lakótelep telep.txt állományban rendelkezésre álló adatait felhasználva néhány kérdésre választ ad.
A képernyőre írást igénylő feladatok eredményének megjelenítése előtt írjuk ki a képernyőre a feladat sorszámát (például: 3. feladat). Ha a felhasználótól kérünk be adatot, akkor jelenítsük meg a képernyőn azt is, hogy milyen adatot várunk. Az ékezetmentes kiírás is elfogadott.
A telep.txt fájl első sora \(\displaystyle N\) és \(\displaystyle M\) értékét adja meg. Az ezt követő \(\displaystyle N\) sor a lakótelep épületeinek szintszámát és a parkokat adja meg.
1. Olvassuk be a telep.txt állományban talált adatokat, és azok felhasználásával oldjuk meg a következő feladatokat.
2. Határozzuk meg, hogy a lakótelep területének hány százaléka park. A választ írassuk ki a képernyőre két tizedes jegy pontosan.
3. Minden sűrűn beépített lakótelepen probléma a kilátás. Egy lakásból addig lehet egy irányba kilátni, amíg a neki megfelelő szintszámnál kisebb házak következnek. Írassuk ki a lakótelep azon lakásainak számát, ahonnan valamelyik irányba ki lehet látni a lakótelepről.
4. Vannak igényes érdeklődök, akik eladó lakást keresnek. Számukra a kilátás és a park vagy a lakótelep szélének szomszédsága értékes. Olvassunk be egy szintszámot és írassuk ki, hogy hány megadott szinten lévő lakás van a lakótelepen, ahonnan több irányba ki lehet látni, illetve ezek közül hány van park vagy lakótelep szélén. Az eredményt a képernyőn a következő formában jelenítsük meg:
5. Városépítészeti szempontból a lakótelep látványa is fontos. Határozzuk meg minden oszlopra és sorra, hogy fentről, lentről, jobbról és balról nézve hány épület látszik. Az épületek a velük azonos vagy kisebb más épületeket eltakarják. Az eredményeket a latvany.txt állományba írjuk ki a következő formában:
6. A városlakók igénylik a minél több és nagyobb zöldterületeket. Olvassuk be a lakótelep egy telkének pozícióját sor, oszlop formában a bal felső sarokhoz képest, és adjuk meg, hogy ott park van-e. Ha igen, akkor a park területének méretét a telkek egységében adjuk meg.
Beküldendő a program forráskódja (i349.pas, i349.cpp, ...) és rövid dokumentációja (i349.txt, i349.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.
(10 pont)
I. 350. Egy 12 csapat részvételével zajló ifjúsági focitalálkozó adatait szeretnénk táblázatkezelő segítségével tárolni, és a csapatok eredményeit kiszámítani. A megoldáshoz három munkalapot használunk, melyek neve Csapatok, Körmérkőzés és Eredmények. A munkalapokon a feladat leírásában szereplő adatoktól és eredményektől jobbra, illetve azok alatt egy oszlop illetve sor kihagyása után tetszőleges segédszámítások végezhetők, de ezen kívül ne használjunk makrókat vagy más saját készítésű programot.
1. A Csapatok munkalap A1:A12 tartományában írjuk be a találkozón résztvevő csapatok nevét (mindenki maga dönti el, hogy mely csapatokat hívja meg).
2. A Körmérkőzés munkalapon a mintának megfelelően két táblázatot készítsünk: a bal oldali tartalmazza a csapatok egymás ellen játszott mérkőzésein a rúgott és kapott gólokat, a jobb oldali pedig a mérkőzések eredményét a szokásos \(\displaystyle \text{rúgott}: \text{kapott}\) formában. A bal oldali táblában adjunk véletlenszerű, 0 és 8 közötti értékeket gólként az egyes mérkőzésekhez a mintának megfelelően, illetve \(\displaystyle -1\) értéket a mérkőzést nem jelentő cellákba. A jobb oldali táblázatban szintén \(\displaystyle -1\) jelentse a szürkével jelölt részeket. Feltételes formázás segítségével a \(\displaystyle -1\)-et tartalmazó cellák háttér és írásszínét állítsuk szürkére.
3. Az Eredmény munkalap A2:A13 celláiban adjuk meg a csapatok nevét, majd mellette számítsuk ki a B oszlopban a rúgott, a C oszlopban a kapott gólok számát, a D oszlopban a gólkülönbséget.
4. Az E, F és G oszlopban határozzuk meg a csapat győzelmeinek, vereségeinek és elért döntetlenjeinek számát.
5. A H oszlopban adjuk meg a csapat által elért pontszámot: minden győzelemért 2, döntetlenért 1 és vereségért 0 pont jár.
6. Az I oszlopban adjuk meg a csapat helyezését, amely a pontok száma alapján történik, illetve pontegyenlőség esetén a jobb gólkülönbség dönt.
7. Az Eredmény munkalap fejlécét a B1:I1 cellákban az előbbi feladatok alapján értelemszerűen adjuk meg.
Teljes pontszámot azok a megoldások kaphatnak, amelyek egy-egy azonos jellegű tartományrészt egy, másolható képlettel határoznak meg. A mintának megfelelő egyszerű szegélyezést alkalmazzuk a munkalapokon szereplő kért táblázatrészeknél, illetve a segédszámításokat tartalmazó tartományokban is.
Beküldendő az i350 táblázatkezelő munkafüzet (.xls, .xlsx, ods, ...), amely tartalmazza a feladat megoldását.
(10 pont)
I. 351. A lap 2014. januári számában megjelent C. 1207. feladatban egy állítást kellett igazolni, amely szerint \(\displaystyle n\ge 5\) egészekre két alakzat területének aránya \(\displaystyle 1:2\)-nél nagyobb. Módosítsuk a feladatot úgy, hogy a két alakzat területének aránya milyen 1-nél nagyobb \(\displaystyle n\) valós számra lesz pontosan \(\displaystyle 1:2\). Vizsgáljuk meg saját készítésű vagy szabadon fölhasználható számítógépes program segítségével, hogy mennyi lesz \(\displaystyle n\) értéke hat tizedes jegy pontossággal, amikor a fenti arány teljesül.
Beküldendő az i351.txt, i351.pdf, ...szöveges állomány, amely megadja \(\displaystyle n\) keresett értékét a kért pontossággal, tartalmazza a megoldás módszerének rövid leírását, és a megoldáshoz használt számítógépes program elérhetőségét és a megoldáshoz használt állományokat, vagy a saját készítésű program forráskódját és a futtatásához szükséges információkat.
(10 pont)
S-jelű feladatokA beküldési határidő 2014. június 10-én LEJÁRT. |
S. 90. Egy barlang több üregből, és az üregeket összekötő járatokból áll. Egy titkos ügynök elrejtett egy nagy értékű kincset a barlang egyik üregében, mi ezt szeretnénk megtalálni. Ismerjük a barlang felépítését: \(\displaystyle 1\ge N\ge 200\;000\) üregből áll, és bármely két üreget választva pontosan egyféleképp tudunk eljutni az egyikből a másikba. Ráadásul úgy szeretnénk megtalálni a kincset, hogy be sem tesszük a lábunkat a barlangba. Kérdéseket tehetünk fel az ügynöknek, méghozzá a következő formában: ,,A kincs az \(\displaystyle i\)-edik üregben van?'' Erre az ügynök megmondja a helyes választ, és ha nem találtuk el, akkor azt is, hogy az üregből melyik irányban keressük a kincset. A probléma abban rejlik, hogy az ügynök nem szereti a fölöslegesen hosszú kérdezősködést. Emiatt az a feladat, hogy minél kevesebb kérdéssel meg tudjuk mondani, hogy hol van a kincs. Teljes pontszámot csak az a program kaphat, amely a minimális számú kérdés feltevésével megoldja a feladatot, akkor is, ha a legtöbb kérdés feltevését igénylő üregben van a kincs. A programnak tehát azt a kérdésmennyiséget kell megadni, ami a lehető legkisebb, de ennyivel garantáljuk, hogy mindenképp kitalálható, hol van a kincs.
A program olvassa be a standard input első sorából \(\displaystyle N\)-et, majd a következő \(\displaystyle N-1\) sorból a barlang alaprajzát: \(\displaystyle a_i\), \(\displaystyle b_i\) egészeket, melyek az \(\displaystyle a_i\)-edik és \(\displaystyle b_i\)-edik üreg közti járatot jelzik. Megoldásként a program írja a standard output első és egyetlen sorába a kérdések számát.
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. A programot több tesztesetre futtatjuk. Nagyon súlyos hibának számít, ha valahol olyan kérdésszámot ír ki, amennyivel nem oldható meg a feladat. Ha több kérdést ír ki, mint az optimális, akkor arra részpontszám kapható. Tehát amit a program kiír, annyi kérdésből mindenképp ki kell, hogy tudjuk találni a kincs helyét.
Részpontszámok a következőkre kaphatóak:
- a program \(\displaystyle N\le 200\)-ra megoldást ad;
- a program \(\displaystyle N\le 5000\)-re megoldást ad.
Beküldendő egy tömörített s90.zip állományban a program forráskódja (s90.pas, s90.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 (s90.txt, s90.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.
(10 pont)
Figyelem!
Az informatika feladatok megoldásait ne e-mailben küldd be! A megoldásokat az Elektronikus munkafüzetben töltheted fel.