Обновлённые 7-е задачи с КЕГЭ-2022

Об обновлениях в ЕГЭ-2022

Единый государственный экзамен по Информатике порадовал и удивил новыми и интересными 7-ми задачками на равномерное кодирование информации, представленными на досрочной и основной волнах, прошедших в апреле и июне соответственно. Экзаменуемые были вынуждены столкнуться с довольно занятными постановками, среди которых можно выделить задачи на сжатие изображений (проценты и пропорции) и задачи на составную глубину кодирования (дополнительные биты контроля чётности и биты степени прозрачности изображений). Очевидно, в виду новизны этих заданий, многие из сдающих экзамен не справились с этими сравнительно простыми задачами, ибо не были готовы к неожиданностям. Изучим же на примерах этих самых задач всю необходимую теорию для их лёгкого и быстрого решения.

Проценты и сжатие

Досрочная волна ЕГЭ-2022 порадовала следующей задачей:

Для хранения произвольного растрового изображения размером 486x720 пикселей отведено 80 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. При сохранении данные сжимаются, размер итогового файла после сжатия становится на 15% меньше исходного. Какое максимальное количество цветов можно использовать в изображении?

При решении задачи без учёта данных о сжатии, получаем:
s = x*y*i <=> 80*1024*8 = 486*720*i <=> i = 80*1024*8/(486*720) <=> i ≈ 1.873
Нам известна глубина кодирования цвета для сжатого изображения, которое на 15% меньше исходного. Возникает вопрос: как найти i для исходного изображения?

Для этого нужно разобрать основные вычислительные задачи с процентами.

1. Найти b = k% от числа n можно так:
   b = n*(k/100).
   Пример: Найти b = 5% от числа 200.
   b = 200*(5/100) = 4.
2. Найти b, если b на k% меньше числа n можно так:
   b = n*(1 - k/100).
   Пример: Какое число b на 15% меньше числа 20?
   b = 20*(1 - 15/100) = 20 - 300/100 = 20 - 3 = 17.
3. Найти b, если b на k% больше числа n можно так:
   b = n*(1 + k/100).
   Пример: Какое число b на 10% больше числа 30?
   b = 30*(1 + 10/100) = 30 + 300/100 = 30 + 3 = 33.

Возвращаясь к нашей задаче, понимаем, что сжатое изображение на 15% меньше исходного, то есть, оно было получено как:
s1 = s*(1 - 15/100) <=> s1 = s*0.85
Отсюда мы получаем, что размер исходного изображения s = s1/0.85.
Тогда изначальная глубина кодирования цвета i = i/0.85 = 1.873/0.85 ≈ 2.203.
Откуда количество цветов = 2^i = 2² = 4.

На основной же волне ЕГЭ-2022 встретилась такая задача:

Для хранения сжатого произвольного растрового изображения размером 640 на 256 пикселей отведено 170 Кбайт памяти без учёта размера заголовка файла. Исходный файл изображения больше, чем сжатый, на 35% (считая размер сжатого файла за 100%). Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?

При решении задачи без учёта данных о сжатии, получаем:
s = x*y*i <=> 170*1024*8 = 640*256*i <=> i = 170*1024*8/(640*256) <=> i = 8.5.
Нам известна глубина кодирования цвета для сжатого изображения, которое на 35% больше сжатого. Возникает вопрос: как найти i для исходного изображения?

Если одно число больше другого на 35%, значит, оно составляет от него 135%. Иначе говоря, s = s1*(1 + 35/100) = s1*1.35.
Тогда i = 8.5*1.35 = 11.475. Количество цветов = 2^11 = 2048.

Составная глубина кодирования

А второй день основной волны ЕГЭ-2022 подарил нам такую задачу:

Для хранения произвольного растрового изображения размером 1024 на 120 пикселей отведено 210 Кбайт памяти без учёта размера заголовка файла. При кодировании каждого пикселя используется 7 бит для определения степени прозрачности и одинаковое количество бит для указания его цвета. Коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов (без учета степени прозрачности) можно использовать в изображении?

Заходит речь о степени прозрачности изображения и определенном количестве бит, отведенных для её определения. Поскольку изображения бывают многослойными (накладываются друг на друга), заходит речь о степени прозрачности их пикселей. Тогда глубина кодирования включает в себя дополнительный канал на кодирование определенного количества уровней прозрачности каждого пикселя.

В задаче требуется найти количество цветов в изображении, для чего необходимо знать глубину кодирования цвета. Поскольку имеется дополнительная информация об отведенных битах для определения степени прозрачности, становится понятно, что глубина кодирования здесь является составной и состоит из двух частей - глубины кодирования цвета и определенном количество битов, отведенных под определение степени прозрачности. Тогда, решая, получаем:
s = x*y*i <=> 210*1024*8 = 1024*120*i <=> i = 210*1024*8/(1024*120) = 14.
Поскольку i = i1 + i2, где i1 - глубина кодирования цвета, i2 - количество бит, отведенных под степень прозрачности, соответственно, а из условия задачи i2 = 7, тогда i1 = i - i2 = 14 - 7 = 7 бит. Тогда количество цветов = 2^7 = 128.

Следующая задача - с резервного дня основной волны ЕГЭ-2022:

Для хранения произвольного растрового изображения размером 1024 на 120 пикселей отведено 210 Кбайт памяти без учёта размера заголовка файла. К коду каждого пикселя дописывается 1 бит четности. Полученные таким образом коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?

Тоже имеем дело с составной глубиной кодирования, где помимо глубины кодирования цвета к коду каждого пикселя дописывается ещё и вторая часть - биты чётности. Биты чётности обычно используются для контроля и проверки того, что передаваемая информация была доставлена точно. Они устанавливаются для каждого кода таким образом, чтобы все коды содержали в себе нечётное или чётное число единиц.

Решая задачу, получаем, что i = 210*1024*8/(1024*120) = 14.
Помним, что i = i1 + i2, где i2 - бит чётности, он по условию 1.
Отсюда глубина кодирования цвета = i - i2 = 14 - 1 = 13.
А количество цветов = 2^13 = 8192.

Выводы

Разнообразие седьмых задач на равномерное кодирование информации возросло - появились новые версии и постановки, включающие в себя дополнительные условия кодирования. Сегодня мы разобрались с самыми актуальными из них, что появились на реальном экзамене в 2022 году =)