Az S. 154. feladat (2021. szeptember)

S. 154. A diákoknak a tanév első matematikaóráján bemelegítésként egy számkereső rejtvényt kell megoldaniuk. Kapnak egy \(\displaystyle N\times M\)-es táblázatot, melyben pozitív egész számok szerepelnek. Egyik sem nagyobb, mint \(\displaystyle K\). A feladat az, hogy segítségeket felhasználva kitalálják, hogy a táblázat melyik mezőjére gondolt a rejtvény készítője. Az első három segítség így hangzik:

1. A keresett szám két különböző prím szorzata.
2. A keresett szám pontosan egy oldalszomszédjánál nagyobb.
3. A keresett szám oszlopában nem szerepel kettőhatvány (\(\displaystyle 1,2,4,8\ldots\)).

Adjuk meg, hány olyan mező van a táblázatban, melyre az állítások mindegyike igaz, vagyis az első három segítség alapján a feladvány megfejtése is lehetne.

Bemenet: az első sor az \(\displaystyle N\), \(\displaystyle M\) és \(\displaystyle K\) számokat tartalmazza. A következő \(\displaystyle N\) sor mindegyike \(\displaystyle M\) számot tartalmaz, rendre a táblázat egy-egy mezőjében szereplő számot.

A kimenet egyetlen sorában adjuk meg, hány olyan mező van a táblázatban, melyre a három állítás mindegyike igaz.

Minta:

Magyarázat: A 6, 10 és a 15 is megfelel az első feltételnek. A 15 minden oldalszomszédjánál nagyobb, a 10-es oszlopában pedig szerepel egy 8-as, így csak a 6-os lehet a megfejtés.

Korlátok: \(\displaystyle 2\le N,M\le 100\), \(\displaystyle 10\le K\le 10^6\). Időkorlát: 0,5 mp.

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

Beküldendő egy s154.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)

A beküldési határidő 2021. október 15-én LEJÁRT.

1. Legyen az \(\displaystyle a\) szám legkisebb prímosztója \(\displaystyle p\). Ez előszámítható minden lehetséges értékre Eratoszthenészi szitával. Az első feltétel akkor teljesül, ha \(\displaystyle a/p\) prím és \(\displaystyle p\ne a/p\)

2. A kettes pontnál a szélekre kellett jobban odafigyelni. Gyakori trükk, hogy a táblázat köré valamilyen alapértékekkel kitöltött "keretet" teszünk. Itt \(\displaystyle 0\) helyett egy kellően nagy számot kellett választani, hogy ne növelje meg a kisebb oldalszomszédok számát.

3. A kettő hatványok előszámíthatók az egyes ponthoz hasonlóan. Emellett eldönthető minden számra ha addig osztjuk kettővel, amíg páratlan számot kapunk. Ha ez \(\displaystyle 1\), akkor kettőhatvány.

Statisztika:

13 dolgozat érkezett.
10 pontot kapott:	Bagladi Milán Zsolt, Nagy 292 Korina, Zádor-Nagy Zsombor.
9 pontot kapott:	Kovács Alex.
1 pontot kapott:	4 versenyző.
0 pontot kapott:	5 versenyző.

A KöMaL 2021. szeptemberi informatika feladatai