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