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 régi honlapot akarom!!! :-)

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