ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > IMPC-2014-15 Questions > задача:


2nd-2. 50512 - Coding redundancy

IMPC-2014-15 Questions

Старт: 22.ноя.2014 в 15:00:00
Финиш: 22.ноя.2014 в 20:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

• 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...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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