Задача 219
Кодирование при несимметричной стоимости

Пусть A и B - двоичные последовательности (последовательности из 0 и 1).
Если A равно length(A) крайним левым битам B, то говорят, что A, является префиксом B.
Например, 00110 является префиксом 001101001, но не 00111 или 100110.

Беспрефиксный код размером n - это такой набор из n отличных битовых последовательностей, в котором ни одна последовательность не является префиксом другой последовательности. К примеру, ниже представлен беспрефиксный код размером 6:

0000, 0001, 001, 01, 10, 11

Теперь предположим, что цена передачи бита '0' - один пенс, а цена передачи бита '1' составляет 4 пенса.
Тогда, общая стоимость выше указанного беспрефиксного кода составляет 35 пенсов, что, как оказалось, является наименьшей возможной стоимостью при несимметричной ценовой политике.
Сокращенно, запишем Cost(6) = 35.

Чему равна стоимость Cost(10^(9))?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net