 |
Az S. 122. feladat (2018. január) |
S. 122. Legyen \(\displaystyle A\) az első \(\displaystyle P\) prímszám halmaza, és \(\displaystyle B\) egy \(\displaystyle N\) elemű, pozitív egészeket tartalmazó halmaz. Készítsünk 1-től kiindulva egy sorozatot, amelyben a sorozat következő tagja az előzőnek egy \(\displaystyle A\)-beli prímmel vett szorzata. Feladatunk az, hogy úgy képezzük a sorozat tagjait, hogy abban a lehető legtöbb \(\displaystyle B\)-beli szám forduljon elő.
Készítsünk programot, amely megadja, hogy adott \(\displaystyle A\) és \(\displaystyle B\) halmaz esetén mennyi a legtöbb olyan \(\displaystyle B\)-beli szám, amely egy szorzással keletkező sorozat tagjaként a fenti módon előállítható. A program standard bemenete \(\displaystyle P\) és \(\displaystyle N\), valamint a következő \(\displaystyle N\) sor mindegyikében egy pozitív egész szám a \(\displaystyle B\) halmazból. A program standard kimenete a képzett sorozatban előforduló \(\displaystyle B\)-beli számok maximális száma.
| Példa bemenet (az újsor karaktereket / jelöli) | Kimenet |
| 3 10 / 5 / 6 / 8 / 10 / 9 / 12 / 21 / 16 / 18 / 24 / | 3 |
Korlátok: \(\displaystyle 2 \le P \le 100\), \(\displaystyle 2 \le N \le 10^6\), a \(\displaystyle B\) halmaz minden eleme \(\displaystyle \le 10^9\).
Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra a programra, amely csak kisebb \(\displaystyle P\) és \(\displaystyle N\) érték esetén ad helyes eredményt 1 másodpercen belül.
Beküldendő egy s122.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.
(10 pont)
A beküldési határidő 2018. február 12-én LEJÁRT.
Mintamegoldásként két versenyző munkáját mutatjuk be:
Az első Gáspár Attila, miskolci, 12. évfolyamos tanuló megoldása: S112ga.cpp.
A második Noszály Áron, debreceni, 10. évfolyamos tanuló megoldása: S122.pdf, s122na.cpp.
A tesztfájlok és a helyes eredmény innen tölthető le: s122beki.zip.
Statisztika:
9 dolgozat érkezett. 10 pontot kapott: Gáspár Attila, Horváth Botond István, Noszály Áron. 8 pontot kapott: 1 versenyző. 6 pontot kapott: 4 versenyző. 1 pontot kapott: 1 versenyző.
A KöMaL 2018. januári informatika feladatai