
ZOJ Problem Set  2892
The discrete wavelet transform is a popular tool for signal compression. In this problem, your job is to write a program to decompress a onedimensional signal (a list of integers) that has been compressed by a simple wavelet transform.
To understand how this simple wavelet transform works, suppose that we have a list of an even number of integers. We compute the sum and difference of each pair of consecutive samples, resulting in two lists of sums and differences each having half the original length. Formally, if the original samples are a(1),..., a(n) the ith sum s(i) and difference d(i) are computed as:
for i = 1,...,n/2: Input The input consists of a number of cases. Each case is specified on a line, starting with an integer N (1 <= N <= 256) indicating the number of samples. The next N integers are the transformed samples. The end of input is indicated by a case in which N = 0. Output For each test case, output the original samples on a single line, separated by a single space. Sample Input
Sample Output
Source: The 2007 ACM Rocky Mountain Programming Contest 