### ACSL Practice 2009

## Task 5: Fax

You are asked to design a *compression scheme* for transmitting fax images of documents. After an image is scanned in using a scanner, you obtain a sequence of numbers where each number *x* takes a value from 1 to 256. For example, an image may be converted into a sequence of the form

1, 1, 1, 25, 26, 25, 25, 255, 256, 256, 256, 255, ...

Since it is not necessary to transmit the exact image, you decide to discretize each number to 4 levels, namely 1, 86, 172 and 256, so that you can code each level using only 2 bits as follows:

Level | 1 | 86 | 172 | 256 |

Code | 00 | 01 | 10 | 11 |

- For the first number in the sequence, you will use the 2 bits as described previously.
- For all other numbers:
- if the previous number is the same as the current number, you will transmit the bit 0.
- otherwise, you will transmit the bit 1 followed by the 2-bit code of the number. That is,
- 1 followed by 00 for number 1
- 1 followed by 01 for number 86
- 1 followed by 10 for number 172
- 1 followed by 11 for number 256

You decide to measure the overall cost of a transmission by the following weighted sum

*cost*=

*total error*+

*W*× (

*total number of bits transmitted*)

- the weight
*W*can be adjusted to give more emphasis to either the total error or the total number of bits transmitted - for an input sequence
*x*1,*x*2, ...,*x**N*and a transmitted sequence*y*1,*y*2, ...,*y**N*, both of length*N*, the total error is Summation (*i*from 1 to*N*) |*x**i*-*y**i*| = |*x*1 -*y*1| + ... + |*x**N*-*y**N*|.

**Example.**For the input sequence 2, 2, 2, 2, 2, 46, 2, 2 with

*W*= 100,

- we can transmit the sequence
*y*1, ...,*y*8 = 1, 1, 1, 1, 1, 86, 1, 1 by transmitting the string 0000001011000 with a cost of 47 + 100 × 13 = 1347; - or we can transmit the sequence
*y*1, ...,*y*8 = 1, 1, 1, 1, 1, 1, 1, 1 by transmitting the string 000000000 with a cost of 52 + 100 × 9 = 952.

### Input

The input consists of several lines. The first line contains two integers *N* (1 ≤ *N* ≤ 50) and *W* (1 ≤ *W* ≤ 100) in this order. Integer *N* denotes the length of the input sequence and integer *W* is the weight. Each of the subsequent *N* lines contains an integer *x* (1 ≤ *x* ≤ 256) of the sequence.

### Output

The output contains a single integer which is the smallest possible cost required to transmit the input sequence with the given value of *W*.

### Sample Input

8 100 2 2 2 2 2 46 2 2

### Sample Output

952

All Submissions

Best Solutions

**Point Value:** 12 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** May 19, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...