新規
編集
添付
時間制限:5000ミリ秒
メモリ制限:65536KB
問題 
貴方はウェーブレット変換の逆変換を記述しなくてはいけない。
この問題で要望されるウェーブレット変換の定義は以下のとおりである。
a(1),,,a(n)までの数列が与えられる。
この数列に対し以下の関数を定義する。
for i=1,,,n/2
s(i)=a(2*i-1)+a(2*i)
d(i)=a(2*i-1)-a(2*i)
この関数を使ってウェーブレット変換がおこなわれる。
具体的な例で示す。
5,2,3,2,5,7,9,6
という数列に対して上記の関数を適用し
s(i)=7,5,12,15
d(i)=3,1,-2,3
という結果が得られる。
この結果を繋げて
7,5,12,15,3,1,-2,3
という新しい数列Bが得られる。
貴方はさらにBの前半分4つ目まで(s(i)で得られた結果)の数列に上記と同様の操作を施し数列を更新しなくてはいけない。
次に更新されたBの半分の半分、前二つの数列に対し同様の操作を施す。
この半分だけ更新していく操作を更新する数列が2つになるまで繰り返す。
この操作の結果貴方は
39, -15, 2, -3, 3, 1, -2, 3
という数列を得る。
操作の過程を図解すると下記の表となる。
5 2 3 2 5 7 9 6 7 5 12 15 3 1 -2 3 12 27 2 -3 39 -15
。
例えば3行目の12,27は上の行の値を足したもの12=7+5,27=12+15であり、. 2、-3は2=7-5,-3=12-15である。
3行目の12,27,2,-3は s(1),s(2),d(1),d(2)という並びとなっている。
前4つの数列に対してだけ操作を施すわけである。
4行目では前2列だけに操作を施している。
39=12+27であり-15=12-27である。
4行目の39,-15はs(1),d(1)の結果である。
表の各列の再下端をつなげたものが最終的な変換結果となる
39, -15, 2, -3, 3, 1, -2, 3が答えである。
貴方はこの変換の逆変換を記述しなくてはいけない。
39, -15, 2, -3, 3, 1, -2, 3
から
5,2,3,2,5,7,9,6を求めるわけである。
入力は行単位で与えられれる。
各行に対して逆変換した結果を一行ずつ出力せよ
各行はまず初めに数列の長さｎが与えられ(ｎは256以下の2の倍数である)、次に数列が与えられる。
n=0が入力の終了である。
入力の例
8 39 -15 2 -3 3 1 -2 3 4 10 -4 -1 -1 0
出力の例
5 2 3 2 5 7 9 6 1 2 3 4
出典
Rocky Mountain 2007
