A rendezés az egyik leggyakoribb számítási feladat. Tekintsük azt a speciális feladatot, amikor a rendezendõ rekordok kulcsa legfeljebb három különbözõ érték lehet! Ilyen feladat például az érmet nyert versenyzõk listájának rendezése úgy, hogy a listában elõször az aranyérmesek, majd
az ezüstérmesek, végül a bronzérmesek szerepeljenek.Most a három lehetséges kulcsérték három egész szám, az 1, a 2 és a 3. A rekordokat (kulcsérték szerint) nem-csökkenõ sorrendbe kell rendezni. A rendezést cserék sorozatával kell elvégezni. A p és q számok által definiált csere alatt azt a mûveletet értjük, amikor az éppen a p-edik pozíción levõ elemet kicseréljük az éppen a q-adik pozíción levõ elemmel.
Feladat:
Adott a kulcsértékek egy sorozata. Írj egy programot, amely kiszámítja a rendezéshez minimálisan szükséges cserék számát! (A részfeladat - Subtask A). Add meg a fenti minimális számú cserét igénylõ rendezést megvalósító cserék egy sorozatát is! (B részfeladat - Subtask B)Bemenet:Az INPUT.TXT fájl elsõ sora a rekordok N számát tartalmazza (1<=N<=1000). A következõ N sor mindegyike egy-egy kulcsértéket tartalmaz.Kimenet:Az OUTPUT.TXT fájl elsõ sorába a rendezéshez minimálisan szükséges cserék L számát írd! (A részfeladat - Subtask A). A következõ L sor a végrehajtott cseréket adja meg a végrehajtás sorrendjében. Minden sor két számot tartalmaz (p-t és q-t), melyek annak a két pozíciónak a sorszámát adják meg, melyek tartalmát fel kell cserélni. (B részfeladat - Subtask B). A pozíciókat 1-tõl N-ig számozzuk.Példa:
INPUT.TXT OUTPUT.TXT 9
2
2
1
3
3
3
2
3
14
1 3
4 7
9 2
5 9
Bizonyos biológiai objektumok szerkezete az alkotórészeik sorozatával írható le. Az alkotórészeket nagybetûkkel jelöljük. A biológusok számára fontos kérdés, hogy egy hosszú sorozat hogyan bontható fel rövidebbekre. Ezeket a rövid sorozatokat primitíveknek nevezzük. Azt mondjuk, hogy egy S sorozat elõállítható primitívek egy adott P halmazával, ha van a primitíveknek egy olyan p1,...,pn sorozata, hogy e sorozat minden tagja eleme a P halmaznak és a sorozat tagjait p1...pn sorrendben összefûzve (konkatenálva) S-et kapjuk. A p1,...,pn sorozatban (S felbontásában) ugyanaz a primitív többször is elõfordulhat, de nem biztos, hogy minden P-beli primitív elõfordul benne. A p1,...,pn primitívek összefûzésén (konkatenálásán) azt értjük, hogy a sorozat elemeit a sorrend megváltoztatása és szóközök nélkül egymás után írjuk. Például az ABABACABAAB sorozat a {A, AB, BA, CA, BBC} primitívekbõl elõállítható. Az S sorozat elsõ K karakterét S egy K hosszúságú kezdõszeletének nevezzük.Feladat:
Írj programot, amely beolvassa a primitívek egy P halmazát és az alkotórészek egy T sorozatát! A program számítsa ki T leghosszabb olyan kezdõszeletének hosszát, amely a P-ben szereplõ primitívekbõl elõállítható!Bemenet:Az input két fájlban található. Az INPUT.TXT a primitívek P halmazát adja meg, míg a DATA.TXT fájl a vizsgálandó T sorozatot tartalmazza. Az INPUT.TXT fájl elsõ sora N-et, a P-ben szereplõ primitívek számát tartalmazza (1<=N<=100). Minden primitívhez két egymás után következõ sor tartozik. Az elsõ sor a primitív L hosszát tartalmazza (1<=L<=20), a második sorban pedig egy nagybetûkbõl ('A'-tól 'Z'-ig) álló, L hosszú string, a primitív leírása található. Mind az N primitív különbözõ.Kimenet:A DATA.TXT fájl minden sorában egyetlen nagybetû áll, az elsõ pozíción. A fájl egy olyan sorral ér véget, mely csupán egy pontot ('.')
tartalmaz.A sorozat hossza legalább 1 és legfeljebb 500,000 (félmillió).
A T sorozat leghosszabb, a P halmazban szereplõ primitívekbõl elõállítható kezdõszeletének a (karakterekben számolt) hosszát kell az OUTPUT.TXT fájl elsõ sorába írni.Példa:
INPUT.TXT DATA.TXT OUTPUT.TXT 5
1
A
2
AB
3
BBC
2
CA
2
BAA
B
A
B
A
C
A
B
A
A
B
C
B
.11
1 2 3 4 8 7 6 5 A bûvös kocka sikere után Rubik úr elkészítette a síkbeli változatot, a bûvös négyzeteket. Ez egy sík lap, amely nyolc azonos méretû négyzetbõl
áll. (lásd a fenti ábrát).Ebben a feladatban azzal a változattal foglalkozunk, amelyben minden mezõ különbözõ színû. A színeket az elsõ nyolc pozitív egész számmal
jelöljük. A lap egy állapota a színek sorrendjének leírásával adható meg, a bal felsõ sarokból indulva és az óramutató járásával azonos irányba haladva. Például az 1. ábrán látható állapot leírása a (1,2,3,4,5,6,7,8) sorozat. Ez a kezdõállapot.A lappal háromféle mûvelet végezhetõ, ezeket az 'A', 'B' és 'C' betûkkel jelöljük.
'A' kicseréli az alsó és a felsõ sort 'B' a téglalap elemeinek körkörös jobbra léptetése (egy mezõvel) 'C' a középsõ négy mezõ körkörös léptetése
az óramutató járásával megegyezõ irányban (egy mezõvel)A fenti három mûvelettel minden állapot elérhetõ.
Feladat:
Írj egy programot, amely elõállítja a mûveletek egy olyan sorozatát, amely az elsõ ábrán látható kezdõállapotból elõállít egy adott célállapotot. (A részfeladat - Subtask A). Egy tesztadatra további két pont jár, ha a program által adott megoldás 300 lépésnél nem hosszabb (B részfeladat - Subtask B).Bemenet:Az INPUT.TXT fájl elsõ sora 8 egész számot tartalmaz, a célállapot leírását.Kimenet:Az OUTPUT.TXT fájl elsõ sorába programodnak a mûveletsorozat L hosszát kell írnia. A következõ L sornak a megoldásban szereplõPélda:
mûveletek azonosítóit kell tartalmaznia, minden sor elsõ pozícióján egy-egy nagybetût.
INPUT.TXT OUTPUT.TXT 2 6 8 4 5 7 3 1 7
B
C
A
B
C
C
B