При записи звука в цифровом виде фактически записываются отдельные отсчеты — значения интенсивности звука в отдельные моменты времени. Для хранения каждого такого значения используется целое неотрицательное число. Таким образом, можно считать, что звуковой файл — это массив из \(n\) целых неотрицательных чисел.
Если в этом массиве ровно \(K\) различных значений, то для записи одного значения требуется \(k = \lceil \log_{2} K \rceil\) бит. Для записи всего файла потребуется \(nk\) бит памяти.
Для сокращения объема памяти, занимаемой звуковым файлом, применяют сжатие. При этом уменьшается количество различных значений интенсивности звука. Для этого выбираются некоторые числа \(l \le r\), и все значения изменяются следующим образом: если число и так лежало в отрезке \([l;r]\), то оно не изменяется. Если число было меньше \(l\), то оно становится равным \(l\); а если было больше \(r\) — становится равным \(r\). Таким образом, теряются очень низкие и очень высокие интенсивности.
Если некоторый элемент массива пришлось изменить при сжатии, скажем, что этот элемент пострадал. Требуется уместить данный звуковой файл на диск размера \(I\) байт, при этом минимизировав количество пострадавших элементов.
Напомним, что в \(1\) байте \(8\) бит.
\(k = \lceil log_{2} K \rceil\) — минимальное целое число такое, что \(K \le 2^{k}\). В частности, если \(K = 1\), то \(k = 0\).
Примечание
В первом примере можно выбрать \(l=2, r=3\). После этого массив примет вид 2 2 2 3 3 3, количество различных значений будет \(K=2\), и звуковой файл поместится на диск. При этом пострадают два элемента.
Во втором примере диск имеет больший размер и исходный файл помещается на него целиком.
В третьем примере мы должны изменить обе 1 или обе 3.