KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

S. 111.

(10 points)

Deadline expired on 12 December 2016.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem S. 111.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley