HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC-2014-15 Questions > problem:


2nd-2. 50512 - Coding redundancy

IMPC-2014-15 Questions

Start: Nov.22.2014 at 03:00:00 PM
Finish: Nov.22.2014 at 08:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 0th-3. 50763 - Valid Password
• 0th-4. 50404 - Sum of Self Powers
• 0th-5. 50692 - How much money?
• 1st-2. 50483 - Group Total
• 1st-3. 50484 - Number Of Letters
• 1st-4. 50473 - Counting Circles Posit...
• 1st-6. 50485 - Center of gravity of ...
• 2nd-1. 50522 - Multiplication Table - 2
• 2nd-2. 50512 - Coding redundancy
• 2nd-3. 50533 - Contacts List
• 2nd-5. 50793 - Top M Customers
• 2nd-6. 50486 - Problems and Progr...
• 3rd-2. 50405 - Accounts Receivable
• 3rd-3. 50474 - Sum of Two Primes
• 3rd-4. 50406 - Draw Pattern 178
• 3rd-5. 50415 - The Scientist
• 3rd-6. 50695 - Longest link between...

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