KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem S. 113. (January 2017)

S. 113. Subscribers can reach the complete after signing in. The text will be public from 28 January 2017.

(10 pont)

Deadline expired on 10 February 2017.


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

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:

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.

Our web pages are supported by:   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