PKU 3444 Wavelet Compression
http://poj.org/problem?id=3444
数列をあるルールに従って繰り返し処理した結果が入力されるので、もとのを復元するというような問題。
入力は多いようだけれど、それにあわせて制限時間もそこそこちゃんとしているようです。
main(){ int n; while(cin>>n,n){ vector<int> in(n); rep(i,n){ cin>>in[i]; } for(int s=1;s<n;s*=2){ vector<int> ba=in; rep(i,s){ in[2*i]=(ba[i]+ba[i+s])/2; in[2*i+1]=(ba[i]-ba[i+s])/2; } } rep(i,n){ if(i)cout<<' '; cout<<in[i]; } cout<<endl; } }