HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Ad-Hoc > problem:


50512 - Coding redundancy

Guest
• Review clarifications (1)

Section problems

• 50325 - How much time passed?
• 50366 - Student Averages (2 Grades)
• 50406 - Draw Pattern 178
• 50416 - Placing Dominoes on Chess...
• 50477 - Character Pyramids
• 50498 - K-Means
• 50505 - kht Puzzle
• 50346 - The Biggest Date
• 50512 - Coding redundancy
• 50528 - Rock-Scissors-Paper
• 50493 - n-digit kth Prime Number
• 50520 - Filling a Matrix Randomly
• 50357 - Convert Euros into Dollars
• 50355 - Bills of City Water Company
• 50454 - What day is it?
• 50350 - Fahrenheit to Celsius
• 50356 - Hours Passed

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Coding redundancy

There are different compression algorithms in image processing. Normal uncompressed images (bitmap images) use 8 bits code representation. Huffman coding is based on coding redundancy and uses variable length code of symbols.

The algorithm prepares the table of symbols according to the frequencies of the symbols. Then, every symbol is assigned a code in such a way that the most frequent symbol is assigned the shortest code and the least frequent symbol is assigned the longer code.

The average length of compressed representation is calculated using the following formula:

where
  • rk is the kth symbol
  • l(rk) is the code length of it and
  • pk(r k) is the probability of the kth symbol

As an example, the following table lists 4 symbols with their frequencies and code lengths.

 Symbol   Length of Code   Frequency 
a 2 0.26
b 1 0.46
c 3 0.24
d 3 0.04

According to the given info, the average length is:

Lavg = (2x0.26) + (1x0.46) + (3x0.24) + (3x0.04) = 1.82

Then, the compression ratio is
C = (Length Before Compression) / (Length After Compression)
C = 8 / 1.82 = 4.396

And coding redundancy is
R = (1-1/C)*100 = (1 - 1/4.396)*100 = 77.25

Question: Write a program that is going to read symbols with their code length and frequencies. Then, your program will calculate and show the coding redundancy.
Note: Length Before Compression is fixed and it's 8.

Input specification
In the beginning, you will be given an integer (n): the number of symbols used where n is between 1 and 200. Then, in each of the following n lines, you will be given three information: a symbol and two numbers.

  • the symbol: at most three chars long string
  • frequency: a floating point number between 0 and 1
  • code length: an integer between 1 and 16

Output specification
Show a floating point number with 2 digits precision.

Sample Input I
4
a 0.26 2
b 0.47 1
c 0.24 3
d 0.03 3
Sample Output I
77.5


Для отправки решений необходимо выполнить вход.

www.contester.ru