PKU 3444-Wavelet Compression

問題概要

数列をある条件でエンコードしたものが与えられる。デコードせよ。

解法

逆から考えて実装する

実装(C)

#include <stdio.h>
#include <stdlib.h>
int n,i,j;
int input[300];
void decode(int x){
	if(x>=n)return;
	int d[300];
	for(i=0;i<x;i++){
		d[2*i]=(input[i]+input[i+x])/2;
		d[2*i+1]=(input[i]-d[2*i]);
	}
	for(i=0;i<2*x;i++){
		input[i]=d[i];
	}
	decode(x*2);
}
int main(void) {
	while(scanf("%d",&n),n){
		for(i=0;i<n;i++)scanf("%d",&input[i]);
		decode(1);
		for(i=0;i<n;i++){
			if(i)putchar(' ');
			printf("%d",input[i]);
		}
		puts("");
	}
}