Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 111. (November 2016)

S. 111. Subscribers can reach the text of the problem after signing in. The text will be public from November 28, 2016.]

(10 pont)

Deadline expired on December 12, 2016.


Sorry, the solution is available only in Hungarian. Google translation

A feladat szövegét értelmezve kiderül, hogy valójában mi a feladat: minden szerelvényre meg kell adni a vagonok kapacitásának legnagyobb közös osztóját.

A legnagyobb közös osztót (lnko) az euklidészi algoritmus segítségével \(\displaystyle O(log(N))\) időben számolhatjuk (lásd a minta kódot).

Az első 2 pont megszerezhető, ha megfigyeljük, hogy \(\displaystyle lnko(a_1,...,a_{k-1},a_k) = lnko(lnko(a_1,...,a_{k-1}),a_k))\) a legnagyobb közös osztó asszociatív (csoportosítható) tulajdonsága miatt, illetve azt, hogy a vonat ebben az esetben veremként működik (hiszen csak az egyik végéhez kapcsolunk, illetve csak onnan kapcsolunk le vagonokat, egyesével). Így az ötlet az, hogy tároljuk egy veremben a legnagyobb közös osztókat. Ha jön egy új vagon, akkor annak a kapacitásának és a verem tetejének legnagyobb közös osztóját beszúrjuk a verem tetejére. Ha egy vagont lekapcsolnak, akkor eltávolítjuk a verem tetejét. így a válasz mindig a verem tetején lesz. Ha ügyesek vagyunk, rájöhetünk, hogy azt az esetet, amikor a vonat üres (a verem üres) könnyen kezelhetjük, ha eredetileg egy egyetlen 0 értéket tartalmazó veremmel indulunk (így az üres verem helyett mindig egy 0-t tartalmazó vermet kapunk, egyébként nem módosítja a választ).

Minta 3 pontért

A további 8 pont megszerzéséhez másképp kell hozzáállni a feladathoz. Először is vegyük észre, hogy ha egy vagon kapacitását 0-ra átírjuk, az olyan, mintha lekapcsoltuk volna (nem befolyásolja a legnagyobb közös osztót). A második fontos megfigyelés az, hogy maximum \(\displaystyle N\)-szer kapcsolunk a szerelvényhez új vagont, így az összhossz maximum \(\displaystyle N\) a lekapcsolt vagonokkal együtt.

Ezeket kihasználva ha egy csupa nullát tartalmazó tömbbel indulunk és mindig meg tudjuk találni a lekapcsolandó vagon indexét, akkor a feladat a következő lesz: Van egy tömbünk, ebben átírhatunk egy tetszőleges elemet, illetve lekérdezhetjük az egész tömb legnagyobb közös osztóját. Ez a szegmensfa klasszikus alkalmazása (ahol a szegmensfa művelete nyilvánvalóan a legnagyobb közös osztó).

Ennek tudatában az első részfeladat megoldását kiterjeszthetjük: Egy kétvégű sort (deque) kell fenntartani a tömbben, illetve egy szegmensfát építeni rá. Ezt könnyen megtehetjük két mutatóval (indexxel), amik a szerelvény első és utolsó vagonjára mutatnak.

A pontos megvalósításhoz lásd a mintamegoldást:

Minta 10 pontért

Minta 10 pontért (szegmensfa pointer-ekkel)


Statistics:

17 students sent a solution.
10 points:Csenger Géza, Csertán András, Dóczi András, Gáspár Attila, Horváth Botond István, Janzer Orsolya Lili, Kiss Gergely, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Vári-Kakas Andor.
9 points:Tóth 827 Balázs.
8 points:1 student.
6 points:1 student.
4 points:1 student.
1 point:2 students.

Problems in Information Technology of KöMaL, November 2016