 |
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 (). 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 (
), míg a második megadja, hogy mennyit hajlandó gyalogolni egy mérkőzés kedvéért (
).
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