|
|||
ShellSort
He made each turtle stand on another one's back Yertle király szeretné átrendezni a teknőstrónját úgy, hogy a legmagasabb rangú nemesei és a legközelebbi tanácsadói közelebb kerüljenek a trón tetejéhez. Egyetlen művelet használható a teknősök kupacbeli sorrendjének a megváltoztatásához: egy teknős előbújhat a helyéről, és felmászhat a többi teknősön keresztül a kupac tetejére. A feladatod, hogy egy teknőskupac eredeti rendezettségének és ugyanazon teknőskupac kívánt rendezettségének az ismeretében meghatározz egy olyan minimális műveletsorozatot, amely átrendezi az eredeti kupacot a kívánt kupaccá. A bemenet specifikációjaA bemenet első sora egy K egész számból áll, amely a tesztesetek számát adja meg. Minden teszteset egy n egész számmal kezdődik, amely a kupacban elhelyezkedő teknősök számát jelenti. A következő n sor a teknőskupac eredeti sorrendjét írja le. Mindegyik sor egy teknős nevét tartalmazza, kezdve a kupac tetején lévő teknőssel, a kupac alján lévő teknős felé haladva. A teknősöknek egyedi nevük van, amelyek nem több, mint nyolcvan karakter hosszúságú, alfanumerikus karaktereket, a szóköz karaktert és a pontot („.”) tartalmazó sztringek. A bemenet következő n sora a kupac kívánt sorrendjét írja le, most is felülről lefelé nevezve meg a teknősöket. Minden teszteset összesen pontosan 2n+1 sorból áll. A teknősök száma (n) kisebb vagy egyenlő lesz, mint kétszáz. A kimenet specifikációjaMinden tesztesetre teknősnevek egy sorozatát kell a kimenetre írni, soronként egy nevet, abban a sorrendben, amelyben a teknősöknek el kell hagyniuk a helyüket a kupacban, és fel kell mászniuk a kupac tetejére. A műveletsorozatnak az eredeti kupacot át kell alakítania a kívánt kupaccá, és a lehető legrövidebbnek kell lennie. Ha egynél több legrövidebb megoldás lehetséges, bármelyik megoldás kiírható. Minden teszteset után egy-egy üres sort is a kimenetre kell írni. Példa bemenet
A példa bemenethez tartozó kimenet
|
|||
| Debreceni Egyetem, Informatikai Kar, v. 2019.03.01. |