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).
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 (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