Статья Автор: Деникина Н.В., Деникин А.В.

Сколько цветов влезет

А если объём задан, а палитра — нет?

Тогда формулу читают справа налево.

Память — это ящик фиксированного размера. Пикселей столько, сколько есть. Вопрос один: сколько бит нужно дать каждому пикселю, чтобы всё поместилось.

Дал больше — не влезло. Дал меньше — влезло, но цветов мало.

Ищем самое большое i, при котором ещё влезает.


Как искать

Переводим лимит в биты. Делим на количество пикселей. Берём целую часть — это i.

Дробную часть выбрасываем без жалости: полбита не бывает.

Лестница двойки: сколько бит — столько цветовi = 12 цветовi = 24 цветовi = 38 цветовi = 416 цветовi = 532 цветовi = 664 цветовi = 7128 цветовi = 8256 цветов2 в степени i — и ни цветом больше

Граница — главная проверка этой темы

Слова «не более», «максимальное количество», «удастся сохранить» означают: ответ стоит вплотную к стенке.

Проверить это можно за десять секунд. Возьми соседнее значение и посчитай объём для него.

Оно обязано не пройти. Если прошло — ты ошибся, и настоящий ответ больше.

Граница: соседнее значение обязано не пройтилимит 512 Кбайтi = 5 → 480 Кбайтвлезаетi = 6 → 576 Кбайтне влезает

Микропаттерн «Граница: соседнее не проходит». Одна лишняя проверка — и половина ошибок этого задания исчезает.


Пример: афиша под лимитом

Афишу 1024 × 768 нужно уложить в 512 Кбайт. Какая палитра максимальна?

  1. Лимит в битах: 512 × 1024 × 8 = 4194304.
  2. Пикселей: 786432.
  3. 4194304 / 786432 = 16/3 — целая часть 5. Значит i = 5.
  4. N = 25 = 32 цвета.

Проверяем границу: при i = 6 вышло бы 576 Кбайт, а это больше 512. Не проходит — значит 32 верно.


Пример

Камера делает фотоснимки 1024 на 768 пикселей. Объём файла с изображением не может превышать 600 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре изображения?

Лимит: 600 × 1024 × 8 = 4915200 бит. Пикселей: 786432. Делим: 25/4 → i = 6. Ответ: 64.

Граница: i = 7 дал бы 672 Кбайт — больше 600. Не проходит.


Пишем программу

Объём ограничен, а спрашивают палитру. Тут тоже хватает одного деления: сколько бит из лимита достаётся каждому пикселю.

Делим целочисленно — знаком //. Он сам отбрасывает дробную часть, а нам именно это и нужно: половину бита пикселю не выдать.

Последняя строка — проверка границы: считаем объём при глубине на бит больше, он обязан выйти за лимит.

▶ Попробуй: смени лимит и посмотри, как прыгает палитра.



Вывод программы:

5
32
576

Ловушки обратной задачи

  • Округлили вверх. «Не более» — это всегда вниз. Вверх округляют только там, где спрашивают «минимальный объём, чтобы хватило».
  • «Минимальное количество цветов». Встречается и такое: тогда объём должен быть больше заданного, и i берут вверх. Читай знак неравенства, а не привычку.
  • Спросили глубину, ответил цветами. «Максимальная глубина цвета в битах» — это i. «Максимальное количество цветов» — это 2i.
  • Прозрачность съела биты. Если на пиксель идут цвет и прозрачность, сначала вычти биты прозрачности, а уже остаток отдай цвету.
  • Несколько изображений в одном лимите. Дели лимит на количество снимков до того, как делить на пиксели.

Регламент для обратной задачи

До счёта. Найди в условии лимит и переведи его в биты. Проверь, на сколько изображений он выдан.

Во время. Раздели лимит на пиксели, возьми целую часть. Если есть прозрачность — вычти её биты.

Перед записью. Спроси себя: просят i или 2i? Проверь соседнее значение — оно должно не проходить.


Проверь себя


Изображение 800 × 600 пикселей должно занять не более 100 Кбайт. Какое максимальное количество цветов можно использовать? В ответе запишите целое число.


Отметьте формулировки, при которых глубину округляют ВНИЗ.


Изображение 1024 × 120 пикселей, отведено 210 Кбайт. На каждый пиксель уходит 7 бит прозрачности и одинаковое число бит цвета. Какое максимальное количество цветов? В ответе запишите целое число.
Печать