Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Рекламный щит

(Время: 1 сек. Память: 16 Мб Сложность: 46%)

Для рекламы своей новой продукции в Китае одна компания решила разместить на небоскребе рекламный щит. Щит состоит из лампочек, организованных в форме прямоугольной сетки из N строк и M столбцов. В любой момент каждая из лампочек может быть либо включена, либо выключена.

Рекламное сообщение состоит из K иероглифов, которые будут показываться один за другим. Для каждого иероглифа известно, какие лампочки должны быть включены при отображении этого иероглифа. Остальные лампочки должны быть выключены.

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

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

Входные данные

В первой строке входного файла INPUT.TXT заданы числа K, N и M (1 ≤ K, N, M ≤ 100) – количество иероглифов в рекламном сообщении, высота и ширина рекламного щита.

Далее, в K∙N строках идет описание иероглифов. Каждый из K иероглифов задается N строками по M символов в каждой. Все эти строки состоят только из символов «*» и «.», «*» соответствует включенной лампочке, «.» – выключенной.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное число групп, на которое можно разбить лампочки.

Пример

INPUT.TXTOUTPUT.TXT
13 2 3
*..
*..
**.
*..
...
.*.
4

Пояснения к примеру

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


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Простые задачи
 Алгоритмы на строках
 Полиномиальный хеш
 A. Функция Эйлера
 B. Обратный элемент
 C. Хеш-функция
 D. Взлом хеш-функции
 E. Рекламный щит
 F. Минимальный сдвиг
 G. Слова
 H. Строки - 3
 I. Подпалиндромы
 J. Циклические сдвиги

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru