与えられた並べ替えを実現するあみだくじの生成
Posted feedbacks - D
とりあえずこんな感じ。 0 1 2 3 4 5 | |-| | | | |-| |-| |-| | |-| |-| | |-| |-| |-| | |-| |-| | 3 5 2 4 0 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | import std.stdio;
import std.string;
void amidaSort(uint[] origList){
auto sortedList = origList.dup.sort;
auto tmpList = origList.dup;
auto amidaRowProto = cast(char[])repeat("| ", origList.length)[0..($ - 1)];
string[] amida;
while(tmpList != sortedList){
for(uint start; start <= 1; start++){
uint[] swap;
for(uint i = start; i < tmpList.length - 1; i += 2){
if(tmpList[i] > tmpList[i + 1]){
swap ~= i;
auto tmp = tmpList[i + 1];
tmpList[i + 1] = tmpList[i];
tmpList[i] = tmp;
}
}
if(swap.length){
auto amidaRow = amidaRowProto.dup;
foreach(i; swap){
amidaRow[(i * 2) + 1] = '-';
}
amida ~= cast(string)amidaRow;
}
}
}
string[] s;
foreach(n; sortedList){
s ~= toString(n);
}
string[] o;
foreach(n; origList){
o ~= toString(n);
}
if(!amida.length){
amida ~= cast(string)amidaRowProto.dup;
}
writefln((s.join(" ") ~ amida.reverse ~ o.join(" ")).join("\n"));
}
void main(){
amidaSort([3, 5, 2, 4, 0, 1]);
}
|
shiro
#4704()
Rating13/13=1.00
お題#4476を見て思いつきました。
0からn (n>=1) までの数字を任意の順で並べたリストが与えられた時、0からnまでが順に並んだ状態から出発して、与えられたリストの順で結果が得られるようなあみだくじを作成して出力するプログラムを書いてください。
与えられたリストが (3 5 2 4 0 1) の場合、出力の1例を示します：
一応、制約条件を示しておきます。
一つのリストに対して複数の解があり得ます。ナイーブな解に飽き足らなければ出力行数をなるべく少なくする解を求める方法を考えてみてください。
[ reply ]