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. 113.

(10 points)

Deadline expired on 10 February 2017.


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

Megállapíthatjuk, hogy ha egy túra kezdő- és végpontja közt megtalálható az összes állat, akkor az összes olyan túra is jó, aminek a kezdőpontja ugyanaz, a végpontja pedig nagyobb. Azaz keressük meg az első elemtől induló túrához az első, feltételeknek megfelelő végpontot. Ha a kezdőpont helyét növeljük, akkor az első lehetséges végpont helye biztosan nem csökken, hiszen

-ha a kezdet növelésével a talált túra során van még ugyanolyan állat, akkor marad a végpont,

-ha nincs, akkor csak továbblépegetve találhatjuk meg az elejéről kieső állatot. Ha elérjük az állatkert végét, akkor nincs több megoldás.

Minden állatfajról tároljuk el, hogy milyen indexű helyeken fordul elő (\(\displaystyle VECTOR\)). Minden állatfajtánál az első indexet a fajtával együtt tegyük be egy \(\displaystyle SET\)-be, ami hely szerint rendez. Ekkor a túrák száma (\(\displaystyle N-az~utolsó~előforduló~index+1\)). Majd vegyük ki a \(\displaystyle SET\) első elemét és az így kieső állatfajt a következő előfordulási helyével tegyük vissza. Az eljárás akkor ér véget, ha a kivett állatfajnak már nincs további előfordulása.

Az algoritmus futásideje \(\displaystyle O(N*log(N))\).


Statistics on problem S. 113.
16 students sent a solution.
10 points:Busa 423 Máté, 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, Molnár Bálint, Nagy Nándor, Németh 123 Balázs, Szakály Marcell, Vári-Kakas Andor.
8 points:1 student.
7 points:1 student.
2 points:1 student.


  • Problems in Information Technology of KöMaL, January 2017

  • 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