Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя Arsenal911

Автор Arsenal911, 12 лет назад, По-русски

Нужно будет сделать программу, сжимающую числа в двоичном коде, о которых, мы знаем, что они находятся в диапазоне от 0 до 255. Или от 1 до 256. Так же мы знаем, что последующее число будет равно или больше предыдущего. То есть мы можем каждое число выразить одним байтом, указав на его месторасположение. Сжимать можно по две, четыре, восемь, шестнадцать, тридцать две и шестьдесят четыре числа. Сжатие пакетное. То есть если сжимать по два числа, то и последующие числа сжимать по два числа. Мы все знаем, если бы числа были бы расположены в случайном порядке, сжатие без потерь было бы невозможно. Но у нас одно преимущество (последующее число будет равно или больше предыдущего). Можно ли использовать это преимущество что бы сжать числа свыше приведённых пакетов используя при этом приведенное ниже количество бит на число.

При сжатии 2 чисел использовать по 7 бит на число.

При сжатии 4 чисел использовать по 6 бит на число.

При сжатии 8 чисел использовать по 5 бит на число.

При сжатии 16 чисел использовать по 4 бит на число.

При сжатии 32 чисел использовать по 3 бит на число.

При сжатии 64 чисел использовать по 2 бит на число.

Кто найдёт алгоритм соответствующим этим условиям вознаграждение 30000 рублей.


Ссылка на источник

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Ну это банально невозможно. Скажем, для двух чисел есть вариантов. А нам предлагают придумать код, в котором для двух чисел будет всего 214 = 16 384 варианта. Тут хоть в миллион рублей премию предлагай, решение не появится. Вообще, уровень сайта прекрасно виден по используемому диалекту «русского» языка.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

пусть n размер блока данных (2, 4, 8 и т.д.) информация о том, что каждое последующее число больше либо равно предыдущего, теоретически, точнее примерно, позволяет нам экономить log_2(n!) бит на блок.
получаем таблицу: размер блока, бит на блок, бит на число.

2 15.000000 7.500000
4 27.415037 6.853759
8 48.700792 6.087599
16 83.749860 5.234366
32 138.336736 4.323023
64 216.004856 3.375076