Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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