Олимпиадный тренинг

Задача . Опорные кадры


Задача

Темы:
Вася разрабатывает прототип цифровой видеокамеры. Видеокамера снимает кадры размером 1920 пикселей по горизонтали и 1080 пикселей по вертикали. Цвета всех пикселей кодируются с использованием палитры из 224 оттенков. Изначально Вася предположил, что будет записывать в память каждый кадр независимо, как последовательность кодов цветов пикселей, используя для записи каждого кода минимально возможное одинаковое для всех пикселей количество бит.  Никакой другой информации, кроме кодов цветов пикселей в память не записывается. Затем Вася стал анализировать результаты и обнаружил, что если разбить последовательность кадров на идущие подряд наборы из 6 кадров, то относительно каждого такого набора справедлива следующая закономерность. Во втором кадре набора оказывается ровно 1 процент пикселей, цвета которых отличаются от цветов пикселей, находящихся на этих же позициях в первом кадре набора. В третьем кадре набора оказывается ровно 2 процента пикселей, цвета которых отличаются от цветов пикселей, находящихся на этих же позициях в первом кадре набора и так далее. То есть, в каждом последующем кадре набора оказывается на 1 процент больше чем в предыдущем кадре набора пикселей, цвета которых отличаются от цветов пикселей, находящихся на этих же позициях в первом кадре набора.

Тогда Вася решил использовать более сложный способ записи данных в память. Для каждого набора он стал сначала записывать опорный кадр – первый кадр набора – как последовательность кодов цветов всех пикселей этого кадра, используя для записи каждого кода минимально возможное одинаковое для всех пикселей количество бит. А затем для каждого из оставшихся 5-ти кадров набора он стал записывать в память только разницу с опорным кадром. Для этого он закодировал все позиции пикселей в кадре и для каждого кадра набора, кроме опорного, стал записывать множество пар
значений: код позиции пикселя, цвет которого изменился, по отношению к цвету пикселя на этой же позиции в опорном кадре и код нового цвета этого пикселя. Для записи каждого кода позиции пикселя Вася использует минимально возможное одинаковое для всех кодов позиций количество бит. Для записи кода цвета Вася использует такое же количество бит, как и для записи кода цвета в опорном кадре. Все получаемые коды Вася записывает подряд побитно. 

Определите, какой выигрыш по памяти получает Вася при новом способе записи данных в памяти для одного набора из
6 кадров. Округлите этот выигрыш в меньшую сторону до целого числа МБайт и запишите в ответ.

Примечание 1МБайт=1024 КБайт, 1 КБайт=1024 байт.

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя