Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 73. feladat (2012. szeptember)

S. 73. Nevenincs városban pingpongversenyt készülnek rendezni. Minden versenyzőről tudjuk a lakhelyét, és azt, hogy mennyit hajlandó gyalogolni egy mérkőzés kedvéért. A város alakja erősen elnyújtott, úgyhogy a pontos lakcím helyett csak azt vesszük figyelembe, hogy a város hosszú főutcájának melyik részéhez lakik közel a versenyző, amit egy házszámmal adunk meg, valamint a gyaloglási távolságot is csak a főutca mentén mérjük. (Azaz úgy tekintjük, hogy bárki el tudja érni a főutcát elhanyagolható idő alatt.)

Két adott lakó között pontosan akkor jöhet létre mérkőzés, ha legalább az egyikük hajlandó elsétálni a másikhoz (a mérkőzést mindenképpen valamelyik játékos lakhelyén kell megrendezni), vagyis a házszámuk közötti különbség legfeljebb akkora, amennyit a lelkesebb fél hajlandó gyalogolni.

Írjunk programot, amely meghatározza, hogy a versenyen hányféle mérkőzés jöhet létre. Két mérkőzést akkor tekintünk különbözőnek, ha nem ugyanaz a két játékos vesz részt benne.

A program a standard input első sorából beolvassa a versenyzők számát (1\le N\le
1\;000\;000). A következő N sorban egy-egy versenyzőről található a két ismert adat, két darab, szóközzel elválasztott szám formájában: az első a lakcíme (1\le
A\le 1\;000\;000), míg a második megadja, hogy mennyit hajlandó gyalogolni egy mérkőzés kedvéért (0\le H\le 1\;000\;000).

A standard outputra írjunk ki egyetlen számot: a lejátszható mérkőzések számát.

Példák:

Pontozás: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 2 pontot ér. A programra akkor kapható meg a maximális 8 pont, ha bármilyen, a feltételeknek megfelelő tesztesetet képes megoldani a 3 mp futási időlimiten belül. Kapható részpontszám, ha a program csak kisebb tesztesetekre tud lefutni időben, továbbá akkor is, ha a program csak olyan teszteseteket tud megoldani, amiknél a versenyzők által megadott gyaloglási távolságok mind azonosak.

Beküldendő egy tömörített s73.zip állományban a program forráskódja (s73.pas, s73.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s73.txt, s73.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2012. október 10-én LEJÁRT.


Négyzetes futásidejű megoldások

Az első megoldási lehetőség, hogy megvizsgáljuk az összes játékospárt, és mindegyikre megállapítjuk, hogy tudnak-e játszani (azaz valamelyikük hajlandó-e elmenni a másikhoz), és ha igen, akkor növelünk egy számlálót, amelyben a végén megkapjuk az eredményt. N játékost N(N-1)/2-féleképpen lehet párosítani, tehát ez a megoldás O(N2) futásidejű, ami nagyobb tesztesetekre nem fér bele a futási időlimitbe.

Még mindig négyzetes, de kicsit gyorsabb megoldást kapunk, ha elérjük, hogy csak az eredménnyel legyen arányos a futásidő, vagyis azon párok számával, akik tudnak egymással játszani. Ha gyaloglási hajlandóság szerint növekvő sorrendbe rendezzük a játékosokat, akkor minden olyan pár, aki játszhat egymással, megteheti ezt úgy, hogy a későbbi játékos sétál el a másikhoz, hiszen ha esetleg a korábbi is elsétálhatna a későbbihez, akkor biztosan megtehetik ezt fordítva is. Tehát ha ebben a sorrendben megyünk végig a játékosokon, akkor elég mindig meghatározni az aktuális játékosra azt, hogy ő kikhez tud az eddigiek közül elsétálni.

Ha rendezve vannak a játékosok lakhely szerint is, akkor megtehetjük, hogy ezen a rendezésen elindulunk az aktuális játékostól (ehhez persze el kell tárolnunk egy külön tömbben, hogy a gyaloglási távolság szerinti rendezésben az i. játékos hol van ezen rendezés szerint) mindkét irányba, és addig lépkedünk, ameddig még olyan játékosnál járunk, akihez el tud sétálni, és közben azokat a játékosokat számoljuk, amelyek a gyaloglási hajlandóság szerinti rendezésben korábban vannak. Ennek az algoritmusnak a futásideje az eredménnyel arányos (hiszen minden játszma miatt legfeljebb két lépést teszünk), ami rossz esetben négyzetes lesz, hiszen ha nagyok a gyaloglási hajlandóságok, akkor a játékosok akár N-nel arányos számú másik játékossal is játszhatnak.

Gyorsabb megoldások

Az előbbi megoldást föl lehet gyorsítani: Fenwick fát használva mindig meg tudjuk mondani az aktuális játékosra gyorsan, hogy az eddidiek közül hány van benne az ő intervallumában.

Néhány versenyző lényegében rájött erre a megoldásra, de az implementáció mindenkinél elég bonyolult volt. Ezen az oldalon található egy jó leírás a Fenwick fáról: Fenwick tree. Az itt leírtak alapján leprogramozott mintamegoldás elég egyszerű, a Fenwick fával dolgozó két függvény összesen csak 10 sort tesz ki: S73-Fenwick-tree.cpp

Ennek a megoldásnak a futásideje O(A+Nlog A), ahol A jelöli a maximális lehetséges lakcímet. Mivel az ezt a megoldást implementálók programjainak futásideje sem fért bele a 3 mp-be, ezért végül 5 mp lett az időlimit. (Viszont a fentebbi mintamegoldás 0,8 mp alatt fut a legnagyobb tesztekre.)

Ha A nagyobb is lehetne

Ha a lakcímek mondjuk 1011 nagyságrendűek is lehetnének, akkor a fentebbi megoldás nem működne, hiszen már a Fenwick fa inicializálása is O(A). Ekkor két lehetőség van:

1. Okosabb adatszerkezetet használunk:

a) A Fenwick fához hasonlóan kettőhatvány hosszú intervallumokra eltároljuk az elemek számát, de csak akkor osztunk föl intervallumot, ha egynél több elem van benne. (Ez hasonlítani fog egy Quadtree-hez, csak egydimenziós.) S73-kdtree.cpp

b) Egy bináris keresőfa csúcsaiban eltároljuk még azt is, hogy hány elem van a csúcs bal részfájában. Összeadva egy elemhez az elem mélységét, és a lelépegetés közben a bal részfák elemszámát, megkapjuk, hogy hány nála kisebb elem van. Ezzel a megoldással az a probléma, hogy ahhoz, hogy gyors legyen, ki kéne egyensúlyozni a fát (pl. AVL fa, Piros-fekete fa), viszont bonyolult frissíteni a bal részfák elemszámát a kiegyensúlyozó műveleteknél. Ez a megoldás leprogramozva kiegyensúlyozások nélkül: S73-bst.cpp (Néha bízhatunk abban, hogy ha egy keresőfa véletlenszerűen épül, akkor kiegyensúlyozás nélkül sem lesz túl nagy az átlagos mélység, de sajnos itt pont nem ez a helyzet, úgyhogy ez a program nem fut le a legnagyobb tesztekre időben.)

2. A játékosoknak egy lakcím szerint rendezett tömbje fölé építjük a Fenwick fát, és ebben bináris kereséssel találjuk ki, hogy mi legyen a Fenwick fához intézett intervallumlekérdezés két végpontja.


Statisztika:

18 dolgozat érkezett.
10 pontot kapott:Nagy Róbert.
9 pontot kapott:Nagy 319 Vendel.
7 pontot kapott:2 versenyző.
6 pontot kapott:3 versenyző.
5 pontot kapott:6 versenyző.
4 pontot kapott:3 versenyző.
3 pontot kapott:2 versenyző.

A KöMaL 2012. szeptemberi informatika feladatai