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

Задача . Плитки


Задача

Темы:
Вася хочет оценить, какой? объем памяти необходим для хранения определенного изображения при использовании различных способов кодирования. Известно, что изображение имеет размеры 640x480 пикселей, причем каждый пиксель может принимать одно из 32768 возможных значений.

При первом способе кодирования Вася хранит только коды цветов пикселей, причем на код каждого пикселя отводится минимальное, одинаковое для всех пикселей количество бит, никакой дополнительной информации не хранится.
Вася заметил, что изображение можно разбить на так называемые “плитки” (непересекающиеся части размером 16х16 пикселей), причем для данного изображения существует всего 50 уникальных плиток, которые встречаются на изображении. Тогда при втором способе кодирования Вася нумерует возможные плитки и кодирует номер каждой плитки с помощью минимального, одинакового для всех плиток числа бит. Также необходимо выделить память под описание возможных плиток, чтобы каждой плитке поставить в соответствие цвета пикселей, ее составляющих. Таким образом, во втором случае Вася хранит словарь возможных плиток (последовательно записывая в память коды пикселей каждой из 50 плиток, используя для каждого пикселя минимальное, одинаковое для всех пикселей изображения количество бит), после чего описывает изображение, записывая в память коды номеров плиток.

Определите, какой из предложенных способов кодирования наиболее эффективен с точки зрения занимаемой памяти. В ответе укажите через пробел два неотрицательных числа: номер наиболее эффективного способа (1 или 2) и целое число КБайт (то есть число бит, округленное до целого числа КБайт в меньшую сторону), сэкономленное по сравнению с другим способом. Например, если первый способ позволяет сэкономить 125 КБайт по сравнению со вторым, в ответе укажите “1 125”. Если экономия памяти составляет менее 1 КБайт, в ответе укажите “1 0” или “2 0”.

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

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

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