Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

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