Az I. 620. feladat (2024. március)

I. 620. Legyen egy helyi értékes számrendszerben az első helyiérték $\displaystyle 1$, a további helyiértékeken pedig a prímszámok növekvő sorozata. Az ebben a számrendszerben felírt $\displaystyle 10101_p$ ötjegyű szám esetén a helyi értékek $\displaystyle 7$, $\displaystyle 5$, $\displaystyle 3$, $\displaystyle 2$, $\displaystyle 1$, azaz a szám értéke $\displaystyle 7\cdot 1+3\cdot 1+1=11$. Tetszőleges nemnegatív egész szám felírható az így megadott számrendszerben, de a felírás nem egyértelmű. Például a $\displaystyle 11$ felírható $\displaystyle 100000_{p}$ alakban is. Tegyük egyértelművé az átváltást úgy, hogy minden esetben azt a felírást választjuk, amelyben csak $\displaystyle 0$-s és $\displaystyle 1$-es számjegy szerepel, és emellett a legkevesebb $\displaystyle 1$-es fordul elő. Így például minden prímszám pontosan egy $\displaystyle 1$-esből és $\displaystyle 0$-kból áll.

Készítsünk programot, amely bekér egy pozitív egész számot, majd megadja a szám felírását a bemutatott számrendszerben. A program a standard bemenet egyetlen sorából olvassa be a számot ($\displaystyle {1\leq a\leq 100\,000}$), majd a standard kimenet egyetlen sorában adja meg a szám felírását a fent leírt módszerrel.

Példák:

A megoldáshoz felhasználható a https://t5k.org/lists/small/10000.txt címen megtalálható szöveges állomány, amely az első 10000 prímszámot tartalmazza. Az állomány letöltés után szerkeszthető, a feldolgozás szempontjából felesleges sorok törölhetők.

Beküldendő egy tömörített i620.zip állományban a program forráskódja és a prímszámokat tartalmazó állomány, valamint egy rövid dokumentáció, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2024. április 15-én LEJÁRT.

Mintamegoldásként Szabó Imre Bence 10. évfolyamos, budapesti versenyző C++ nyelven készült megoldását (i620.cpp, primszamok.txt), valamint Farkas Roland 12. osztályos, egri tanuló megoldását (i620.py, 10000.txt) adjuk közre.

Statisztika:

18 dolgozat érkezett.
10 pontot kapott:	Farkas Roland, Szabó Imre Bence.
8 pontot kapott:	6 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
0 pontot kapott:	6 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	2 dolgozat.

A KöMaL 2024. márciusi informatika feladatai