Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1493
DPCM Encoding

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One of the widely-used technologies in voice signal compression is DPCM encoding. The algorithm is very simple, yet it's quite effective in signal transferring.

Given the original voice signals: a1, a2, a3, a4, ..., an, you are supposed to calculate the compressed data bi according to the following equations:

with the initial condition: a0 = b0 = 0, where ai is an 8-bit unsigned integer and bi is a 4-bit signed integer, the highest bit is used to represent its sign.

By applying this method one can successfully achieve 50% compression ratio. Now you are asked to implement this algorithm - please keep in mind that this is going to be used in a real-time system, so your program should be efficient enough to process 64kb data every second.


The input consists of several cases, each starts with an even number n (n <= 10000), indicating the number of the bytes to be processed, then followed by n bytes in hex form.

The input is ended by EOF.


For each test case, output the number of bytes in DPCM in a line, then output the n bytes in hex form, with 8 numbers per line.

Sample Input

01 FF 09 07 06 FE
FD 00 09 F8 02 03 00 01
02 0B FA 08

Sample Output

17 1e f7
79 77 8d d1 17 78

Author: TANG, Jiqing
Source: ZOJ Monthly, February 2003
Submit    Status