 |
Az S. 58. feladat (2010. december) |
S. 58. A Bergengóc Királyságban évezredes hagyományokkal rendelkező esemény a Nemzetközi Máguskonferencia, melynek minden évben az egyik legkedveltebb és leglátványosabb műsorszáma a Nagyotmondók Viadala. Ennek keretében az ország legkiválóbb mágusai mérik össze tudásukat: a nyertes az, aki a rendelkezésre álló időkeret alatt a leghosszabb varázsszót mondja ki -- a legkülönfélébb csodás mellékhatásokkal.
Sajnos az előző évben a rendezvény túlontúl látványosra sikeredett, s a konferencia után a főváros helyreállítása hónapokig tartott. Ennek megelőzése érdekében a király idén elrendelte, hogy a versenyen kizárólag olyan varázsszavakkal lehet indulni, melyek előállnak páros hosszú tükörszavak egymás után írásával, ezekről ugyanis köztudott, hogy veszélytelenek.
Készítsünk programot, mely a versenyzők által előadni kívánt, előzetesen leadott varázsszavakról eldönti, hogy a fenti módon felbonthatók, azaz a versenyen biztonsággal előadhatóak-e, és ha igen, akkor meg is ad egy-egy ilyen felbontást.
A standard bemenet első sorában egyetlen egész szám: a vizsgálandó varázsszavak N száma szerepel (1
N100), azt ezt követő N darab sor pedig egy-egy varázsszót tartalmaz. Feltehetjük, hogy minden varázsszó kizárólag az angol ábécé kisbetűiből áll, legfeljebb 1 000 000 karakter hosszú, illetve -- amennyiben biztonságos -- legfeljebb 5000 karakter hosszú tükörszavakból épül fel.
A standard kimenetre pontosan N darab sor kerüljön, az i-edik sor a bemenet i-edik varázsszavának értékelését tartalmazza. Amennyiben a varázsszó biztonságos, akkor a sor elején a felbontásban szereplő részszavak K száma szerepeljen (K
1), majd ezt kövessék a felbontás elemei, szóközzel elválasztva. Ellenkező esetben a sorba mindössze egy ,,0'' számjegyet írjunk. Több megoldás esetén bármelyik megadható.
Beküldendő a feladat megoldását tartalmazó forrás és projektállományok (az .exe és más a fordító által generált kiegészítő állományok nélkül), valamint a megoldás menetét röviden bemutató dokumentáció (s58.txt, s58.pdf, ...) egy tömörített mappában (s58.zip).
(10 pont)
A beküldési határidő 2011. január 10-én LEJÁRT.
Megoldás
Még ha egy részszóról gyorsan el is tudnánk dönteni, hogy tükörszó-e, akkor is felmerül a kérdés: hogyan tudunk hatékonyan meghatározni egy olyan felbontást, amelynek minden eleme tükörtulajdonságú?
Szerencsére a mohó módszer itt működik: megtehetjük, hogy a varázsszó egyre növekvő hosszúságú kezdőszeleteiről megvizsgáljuk, hogy tükör-e, és ha igen, levágjuk, majd a maradékra újból ugyanezt végezzük. Ha sikerül elfogyasztani a varázsszót, pontosan akkor biztonságos.
Ez helyes. Az egyedüli nehéz irány annak megmutatása, hogy ha van felbontás, akkor azt meg is találjuk. Ez pedig igaz, hiszen ha az algoritmusunk nem a felbontás első darabját, w-t találja meg, akkor annak egy v kezdőszeletét találhatta csak meg (hiszen növekvő hossz irányában dolgozik). Ha |v||w|/2, akkor w tükörtulajdonsága miatt w=vxx'v' alakú, ahol x w első felének azt a részét jelöli, melyet v nem fed le, az aposztróf pedig a tükrözés. Ekkor viszont a felbontásban w-t lecserélhetjük v, xx' és v'-re, hiszen egy tükörszó tükrözöttje is tükörszó, tehát van olyan felbontás is, melynek v az első eleme.
Hasonlóan, megmutatható hogy |v|>|w|/2 nem lehetséges, mert akkor már korábban kellett volna egy tükörszó kezdőszeletet találnunk.
Ezek után az egyetlen kérdés, hogy miként döntsük el egy kezdőszeletről, hogy tükörszó-e. Ezt Manacher jól ismert algoritmusával a varázsszó hosszában összesen lineáris időben meghatározhatjuk.
Statisztika:
10 dolgozat érkezett. 10 pontot kapott: Barta 111 János, Borsos 607 Zalán, Szabó 928 Attila. 8 pontot kapott: 4 versenyző. 7 pontot kapott: 1 versenyző. 6 pontot kapott: 2 versenyző.
A KöMaL 2010. decemberi informatika feladatai