0223. Квадродерево

Имя входного файла:	quadro.in
Имя выходного файла:	quadro.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

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

Опишем суть этой структуры данных. Квадродерево позволяет нам представлять в памяти таблицу размера 2ⁿ*2ⁿ, состоящую из нулей и единиц. Все дерево состоит из ячеек, каждая ячейка отвечает за некоторую часть этой таблицы, при этом каждая часть является квадратом со стороной 2^p. Первая ячейка отвечает за всю таблицу.

Если все элементы квадрата, за который отвечает ячейка, имеют одинаковое значение (0 или 1), то в ячейке просто хранится эта информация. Если же внутри квадрата существуют хотя бы два различных элемента, то весь квадрат делится на четыре непересекающихся квадрата со стороной 2^{p - 1}, после чего для каждой четверти создается отдельная ячейка, и ссылки на все четыре созданных ячейки записываются в ячейку, отвечающую за большой квадрат.

Правильное квадродерево для данной таблицы. Любой квадрат, у которого все четыре стороны выделены, является ячейкой квадродерева. Всего используется 13 ячеек. \end{center}

Далеко не всегда подобный способ хранения таблицы приводит к сокращению объема памяти. Но не во всех задачах требуется абсолютно точно хранить всю таблицу, не потеряв значения ни одного элемента. Иногда можно потерять часть информации. А именно, разрешается изменить значения не больше, чем k элементов таблицы.

Выясните, какое минимальное возможное количество ячеек может быть в квадродереве, описывающем таблицу, получающуюся из данной изменением не более, чем k элементов.

Формат входного файла

Первая строка входного файла содержит два целых числа t=2ⁿ и k – размер таблицы и максимальное количество измененных ячеек соответственно (2 ≤ t ≤ 128, 1 ≤ k ≤ t²).

Гарантируется, что t является степенью двойки.

Следующие t строк содержат по t символов, каждый из которых является 0 или 1. Эти строки описывают заданную таблицу.

Формат выходного файла

Выведите в выходной файл одно целое число – минимальное возможное количество ячеек в квадродереве, описывающем таблицу, получающуюся из данной изменением не более, чем k элементов.

Пример:

quadro.in	quadro.out
4 2 0001 0010 0000 0010	9

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

Для ее хранения с помощью квадродерева необходимо 9 ячеек: одна для всей таблицы, четыре для четырех квадратов $2 \times 2$, три из них содержат 0, а четвертый, соответствующий нижнему правому углу, разбивается еще на четыре.

Источник: Командное школьное первенство Республики Карелия по программированию, 30 октября 2011.

Обсудить       Отправить решение



Версия для печати