[shkola] Edna zadacha za domashno

Sorry, za loshoto oformlenie poluchilo se pri copy&paste-a!
Razpolagam s testowi primeri (originalnite), taka che ako nqkoi iska da 
si testwa reshenieto, mozhe da mi go prati ili da poiska da mu pratq 
testowete!

Ivo

==========
Description. 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, 1, 1, 46, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 
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


 Then you realize that large areas of the same value (e.g. white) often 
occur in documents resulting in long sequences of very similar numbers. 
You decide to adopt a compression scheme as follows: 
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.
 Finally, since you are not worried about a small amount of error, you 
realize that you can improve your scheme by ignoring isolated changes. 
For example, if the input sequence is 2, 2, 2, 2, 2, 46, 2, 2 and you 
transmit the sequence 1, 1, 1, 1, 1, 86, 1, 1, the total error will be 
1 + 1 + 1 + 1 + 1 + 40 + 1 + 1 = 47 and the string that needs to be 
transmitted is 0000001011000. If, instead you choose to transmit the 
sequence 1, 1, 1, 1, 1, 1, 1, 1, the total error will be 1 + 1 + 1 + 1 
+ 1 + 45 + 1 + 1 = 52, but the string that needs to be transmitted 
would be 000000000 which is shorter. 

You decide to measure the overall cost of a transmission by the 
following weighted sum 
cost = total error + W × (total number of bits transmitted) 
where 
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 x1, x2, …, xN and a transmitted sequence y1, y2, 
…, yN, both of length N, the total error is Summation (i from 1 to N) 
|xi - yi| = |x1 - y1| + … + |xN - yN|. 

Example. For the input sequence 2, 2, 2, 2, 2, 46, 2, 2 with W = 100, 
we can transmit the sequence y1, …, y8 = 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 y1, …, y8 = 1, 1, 1, 1, 1, 1, 1, 1 by 
transmitting the string 000000000 with a cost of 52 + 100 × 9 = 952. 
In this case, the second option has lower cost. 

Input. The input file FAX.IN 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. For example, the input file 
                8 100
                2
                2
                2
                2
                2
                46
                2
                2 
 represents the 8-number sequence 2, 2, 2, 2, 2, 46, 2, 2 with W = 100. 

Output. The output file FAX.OUT contains a single integer which is the 
smallest possible cost required to transmit the input sequence with the 
given value of W. For the input sequence given in the above example, 
the output file should contain the number 
                952

Other related posts: