Az S. 152. feladat (2021. április)

S. 152. A LONG teniszbajnokságra \(\displaystyle 2N-1\) versenyző nevezett. Közülük kell kiválasztani a legjobb \(\displaystyle N\) játékost, akik díjat kapnak. A sok nevezőre való tekintettel nem szeretnének mindenkit egyszerre versenyeztetni, ezért a versenyt több napon keresztül bonyolítják le. A versenyzők egy várólistára kerülnek, és hogy melyik nap és kivel játszanak meccset, azt a következők szerint határozzák meg.

Az első nap a várólista első \(\displaystyle N\) versenyzője versenyez egymással egyenes kiesésben, azaz, ha valaki veszít, aznap már nem játszhat. Ők megkapják az \(\displaystyle 1,2,\ldots, N\) sorszámokat. Egy nap több körből áll, és egyszerre csak egy meccset játszanak. Mindig az a két játékos játssza a következő meccset, akik még nem játszottak az adott körben és a sorszámuk a legkisebb. (Első a másodikkal, harmadik a negyedikkel stb. ebben a sorrendben.) Minden kör végén, ha valaki partner nélkül marad, akkor továbbjut a következő körbe. Ezt addig csinálják, amíg már csak egy versenyző marad, ő lesz a nap győztese.

Egy mérkőzés győztese az a versenyző, aki ,,több trükköt ismer''. Egyenlőség esetén a mérkőzés aznapi sorszáma dönt. Ha ez páratlan, akkor a kisebb sorszámú versenyző nyer, ha páros, akkor a nagyobb sorszámú.

Minden nap végén kiosztják a díjakat. Elsőként a nap győztese kap díjat, majd azok a versenyzők, akiket a győztes ejtett ki, a kiesés szerinti fordított sorrendben egy-egy pontot kapnak. (A pontok a napok során összeadódnak.) Ha valaki így összegyűjt két pontot, és még nincs meg az \(\displaystyle N\) számú díjazott, akkor ő is díjazottá válik.

Ha még nincs meg az \(\displaystyle N\) számú díjazott, akkor újabb nap következik. Ezen a napon szintén \(\displaystyle N\) versenyző játszik. Az előző napon díjazottak helyére a díjazás sorrendjében bekerülnek a várólistáról a következő olyan játékosok, akik még nem versenyeztek. Ha például a hármas sorszámú versenyző nyert, és az előző napon még a kettes és ötös is díjat kapott ebben a sorrendben, akkor a következő három versenyző a várólistáról a hármas, kettes és ötös sorszámmal versenyez ezen a napon.

Bemenet: az első sor az \(\displaystyle N\) számot tartalmazza. A második sor \(\displaystyle 2N-1\) pozitív számot tartalmaz. Az \(\displaystyle i\)-edik szám a várólistán \(\displaystyle i\)-edik versenyző által ismert trükkök számát adja meg.

Kimenet: a kimenet \(\displaystyle i\)-edik sora az \(\displaystyle i\)-edik napon díjazottak számát, majd a díjazott(ak) sorszámát tartalmazza a díjazás sorrendjében.

Példa:

Magyarázat: az első nap mérkőzései \(\displaystyle \text{mérkőzés sorszáma} : \text{győztes} -\text{vesztes}\) formátumban: \(\displaystyle 1:1-2\), \(\displaystyle 2:4-3\), \(\displaystyle 3:1-4\), \(\displaystyle 4:1-5\), győztes: 1., pontot kap: \(\displaystyle 5,4,2\). Új játékos 2 trükkel az 1. sorszámú helyre. A második nap: \(\displaystyle 1:2-1\), \(\displaystyle 2:4-3\), \(\displaystyle 3:4-2\), \(\displaystyle 4:4-5\), győztes: 4., pontot kap: \(\displaystyle 5,2,3\). Új játékosok \(\displaystyle 5,1,4\) trükkökkel a \(\displaystyle 4,5,2\) helyekre. A harmadik nap: \(\displaystyle 1:2-1\), \(\displaystyle 2:4-3\), \(\displaystyle 3:4-2\), \(\displaystyle 4:4-5\), győztes: 4., pontot kap: \(\displaystyle 5,2,3\). A 3. sorszámú versenyző már nem kap díjat, mert megvan az \(\displaystyle N\) díjazott.

Korlátok: \(\displaystyle 1\le N\le 32\,768\), \(\displaystyle 1\le \text{ismert trükkök száma}\le 1024\). Időkorlát: 1 mp.

Értékelés: A pontok 50%-a kapható, ha \(\displaystyle N< 100\).

Beküldendő egy s152.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. május 17-én LEJÁRT.

A feladat a tournament fából nyert inspirációt, így a leghatékonyabb megoldások ezt az adatszerkezetet használták. Megjegyezzük, hogy a feladat megoldható hagyományos szegmensfával is. A csúcsokba érdemes eltárolni a győztest és egyéb adatokat, amik a megoldás során kellhetnek. (A nyertes aznapi rajtszáma stb.) Ha a levelekbe a versenyzőket írjuk, a fát felépítve a gyökérbe a győztes kerül. Ezután a fában a győztes meccsein visszalépkedve kioszthatjuk az aznapi pontokat és felvesszük, ki helyére kell új versenyzőt hívni. Ezután a megfelelő versenyzők helyére újakat teszünk és jön a következő versenynap. Figyeljünk, hogy csak azokat a csúcsokat számoljuk újra, amik alatt változás történt.

Így az amortizált futási idő nem lesz túl nagy, hiszen minden versenyző kivételekor legfeljebb \(\displaystyle log(N)\le 16\) lépést teszünk lefelé és minden csere után legfeljebb ugyan ennyi csúcsot kell újraszámolni.

Komplexitás: \(\displaystyle O(N*log(N))\)

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Varga 256 Péter.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	1 versenyző.

A KöMaL 2021. áprilisi informatika feladatai