A KöMaL 2021. januári informatika feladatai

I-jelű feladatok A beküldési határidő 2021. február 18-án LEJÁRT.

I. 526. András szereti az egész számokat és a számrendszereket. Azon töprengett, hogy vannak-e olyan számok, amelyeket több különböző alapú számrendszerben felírva a számjegyek összege ugyanaz az érték. Hamar rájött, hogy például az 1 szám felírása mindegyik számrendszerben 1, tehát a számjegyek összege is azonos. A 2 szám alakja 2-es számrendszerben 01, minden más számrendszerben 2, vagyis a számjegyek összege egy kivétellel itt is 2. Gondolta, hogy az egyjegyű számoknál ez nem olyan érdekes tulajdonság, ezért a többjegyűekkel kezdett foglalkozni. Sokat számolt, de rájött, hogy a témakört alaposabban csak számítógépes programmal tudná megvizsgálni.

Segítsünk Andrásnak. Készítsünk programot, amely megadja azokat a tízes számrendszerben legalább kétjegyű, de legföljebb hatjegyű pozitív egészeket, amelyeknek a lehető legtöbb számrendszerben azonos a számjegyeinek összege. A program a kimenet első sorába írja ki, hogy legföljebb hány számrendszerben azonosak a számok, majd a következő sorba növekvő sorrendbe írja ki ezeket a számokat. A program csak a kettestől a tízesig terjedő számrendszerekben vizsgálódjon.

Beküldendő egy i526.zip tömörített állományban a forrásprogram és egy rövid dokumentáció, amely megadja, hogy a program melyik fejlesztői környezetben fordítható.

(10 pont)

megoldás, statisztika

I. 527. (É). Egy társaságban többen vannak, akik különböző helyekről ismerik egymást, de vannak szép számmal olyanok is, akik még sohasem találkoztak. Az ismeretségek kölcsönösek.

Zoltán nagyon érdeklődik a gráfok iránt, ezért gyorsan feltérképezi a társaságot az ismeretségek alapján. Egy papírra feljegyzi az egymást ismerők monogramját a következő formában: KP NZ JJ SA NZ BC \(\displaystyle \ldots\ \)A leírásban párok fordulnak elő, tehát KP és NZ ismeri egymást, JJ és SA ismeri egymást \(\displaystyle \ldots\ \) A monogramok minden esetben az angol ABC két nagybetűjéből állnak, és nincs két azonos monogrammal jelölt személy. Minden ismeretség csak egyszer kerül feljegyzésre, és teljesen véletlenszerű, hogy melyik fél szerepel azon elsőként vagy másodikként.

Zoltán később több kérdést is megfogalmazott, amely az ismeretségekre vonatkozik. Mivel a társaság elég nagy, ezért úgy gondolta, hogy a kérdésekre előbb választ kaphat, ha számítógépes programot készít. Segítsünk neki, oldjuk meg a következő feladatokat.

1. A párok monogramjai a honlapunkról letölthető parok.txt szöveges állomány egy sorában vannak egy-egy szóközzel elválasztva, legföljebb 500 monogram, azaz 250 ismeretség. Olvassuk be és tároljuk el a további feldolgozáshoz a monogramokat és az ismertségeket. Részlet a parok.txt állományból:

KP NZ JJ SA NZ BC MP AC BJ KC KJ MP ...

2. Adjuk meg, hogy hány személy szerepel az állományban.

3. Kérjük be egy személy monogramját, és adjuk meg a monogramjaik ABC-sorrendjében az ismerőseit.

4. Adjuk meg, hogy melyik személynek van a legtöbb ismerőse a társaságban. Ha több ilyen személy van, akkor elegendő az egyiket megadni: írjuk ki a monogramját és ismerőseinek számát.

5. Kérjük be egy másik személy monogramját, és adjuk meg, hogy hány közös ismerőse van az előbbi feladatban bekért személlyel.

6. Adjuk meg, kik azok, akik nem ismerik az előbb bekért személyt és annak egyetlen ismerősét sem.

Beküldendő egy tömörített i527.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ő állomány: parok.txt.

(10 pont)

megoldás, statisztika

I. 528. Évről-évre új naptárt készítünk és ragasztunk a falra, holott csak 14 különböző hételrendezésű év létezik, ha a mozgó vallási ünnepek időpontjától (húsvét, pünkösd, purim stb.) eltekintünk.

Készítsük el az azonos naptárú éveket megadó listát táblázatkezelő segítségével naptárak néven.

Az A1 és B1 cella legyen a minta szerinti, az A2 cella kezdetben legyen üres, de a minta szerinti formátumú.

Ha az A2 cellába begépelünk egy 2000 és 2399 közötti egész számot, a B2 cellától kezdődően növekvő rendezettséggel jelenjenek meg azok az évszámok, amelyek 2000 és 2399 közé esnek, és naptáruk azonos az A2 cellába írt évszámú év naptárával. Állítsuk be, hogy a formátum a mintának megfelelő legyen.

Ügyeljünk arra, hogy amennyiben az A2 cella üres vagy tartalma nem a 2000–2399 tartományba eső egész szám (pl. 25, 4,31, ,,Martfű'', HAMIS), a B oszlopban ne jelenjen meg semmi a keretezett, színezett mezőkben.

Segédszámításokat végezhetünk a C oszloptól jobbra, amelyek értelmezését feliratokkal segítsük elő vagy a dokumentációban írjuk le. A megoldásban saját függvény vagy makró nem használható.

Beküldendő egy i528.zip tömörített mappában a táblázatkezelő munkafüzet és egy rövid dokumentáció, amelyben szerepel a megoldáshoz alkalmazott táblázatkezelő neve, verziószáma.

(10 pont)

megoldás, statisztika

I/S-jelű feladatok A beküldési határidő 2021. február 18-án LEJÁRT.

I/S. 50. Egy televíziós vetélkedő döntőjében két vagy három versenyző szerepel. A végső sorrendet közönségszavazással határozzák meg. Mindenki csak egy versenyzőre és legfeljebb egyszer szavazhat. A szavazás vége előtt öt perccel megmutatják az addig leadott szavazatok százalékos eloszlását. Pontosabban század százalékra kerekítve kiírják az állást anélkül, hogy megmondanák, melyik szám melyik versenyzőhöz tartozik.

Peti már biztosra tudja ki fog nyerni (a kedvenc versenyzője), így arra kíváncsi, mit tudhat meg még a számokból. Most azt szeretné megtudni, hogy legalább hányan adták le a szavazatukat a döntőben. Készítsünk programot, amely válaszol Peti kérdésére több ilyen vetélkedő esetén.

Bemenet: az első sor a vetélkedők, azaz a megoldandó esetek \(\displaystyle N\) száma. Ezután \(\displaystyle N\) sorban egy-egy lehetséges állás szerepel, mindegyikben legfeljebb három, a mintával megegyező formátumú szám.

Kimenet: a legkisebb szavazószám, amire igaz, hogy létezik olyan szavazateloszlás, amely a kiírt százalékos értékeket adja.

Korlátok: \(\displaystyle 1\le N\le 100\). Időkorlát: 0,1 mp.

Példa:

Figyelem: a kerekített számok összege nem feltétlenül ad 100%-ot.

Értékelés: A pontok 40%-a kapható, ha a döntőben két versenyzőre lehet szavazni. További 60% kapható, ha a versenyzők száma három.

Beküldendő egy is50.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ői környezetben futtatható.

(10 pont)

megoldás, statisztika

S-jelű feladatok A beküldési határidő 2021. február 18-án LEJÁRT.

S. 149. Adott egy \(\displaystyle N\) csúcsból álló fa, csúcsait pozitív egész számokkal jelöljük, gyökere az 1-es csúcs. A fa minden \(\displaystyle P\) csúcsára szeretnénk tudni, hogy hányféleképpen tudunk kiválasztani a fából egy \(\displaystyle K\) darab csúcsból álló rendezett sorozatot úgy, hogy az abban szereplő csúcsok legközelebbi közös őse a \(\displaystyle P\) csúcs legyen. Két kiválasztás különböző, ha abban a választott csúcsok eltérőek, vagy ha a csúcsok sorrendje különböző. A választásban egy csúcs többször is előfordulhat. A \(\displaystyle K\) darab csúcs legközelebbi közös őse az a csúcs, ami őse a \(\displaystyle K\) csúcs mindegyikének, és a lehető legmesszebb van a gyökértől.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) és a \(\displaystyle K\) számot. A következő \(\displaystyle N-1\) sor mindegyike egy \(\displaystyle x\) és \(\displaystyle y\) számot tartalmaz, ami azt jelenti, hogy közöttük fut él.

Kimenet: adjunk meg egy sorban \(\displaystyle N\) darab számot. Az \(\displaystyle i\)-edik szám jelentse a megoldást akkor, ha \(\displaystyle P=i\). A megoldások nagyon nagyok is lehetnek, ezért azok számának modulo \(\displaystyle 10^{9}+7\) maradékát adjuk meg.

Példa:

Magyarázat: nézzük \(\displaystyle P=2\) esetét (\(\displaystyle K=2\), tehát két csúcsot kell sorrendben választani, amelyek legközelebbi közös őse a 2-es csúcs). A lehetséges kiválasztások: 2-2, 2-3, 2-7, 2-4, 2-5, 3-2, 3-4, 3-5, 7-2, 7-4, 7-5, 4-2, 4-3, 4-7, 4-5, 5-2, 5-4, 5-3, 5-7.

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 2\le K\le {10}^{10}\), \(\displaystyle 0\le xy\le N-1\). Időkorlát: 0,4 mp.

Értékelés: a pontok 30%-a kapható, ha \(\displaystyle K \le 2\).

Beküldendő egy s149.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ői környezetben futtatható.

(10 pont)

megoldás, statisztika