Задача g6_1055: Кубики (XV Всеукраинская олимпиада по информатике)
Трехмерная фигура состоит из единичных кубиков. По фигуре можно построить ее фронтальную и правую проекции. Очевидно, что по этим двум проекциям не всегда можно восстановить фигуру.
Задача
Напишите программу CUBES, которая получает на вход фронтальную и правую проекции фигуры и определяет минимальное и максимальное количество кубиков, которое можно было бы использовать для построения фигуры с заданными проекциями.
Входные данные
В первой строке входного файла CUBES.DAT находятся три числа N, M и К, которые задают размеры проекций (1 < N, M, K < 100). Дальше задаются две проекции: сначала фронтальная, а затем правая. Проекция задается N строками, каждая из которых состоит из чисел 0 и 1, разделенных пробелами. Для фронтальной проекции таких чисел будет M, а для правой - K. 0 означает свободную клетку проекции, 1 - заполненную.
Пример входных данных
2 2 3
1 0
1 1
0 0 1
1 1 1
Выходные данные
В единственной строке выходного файла CUBES.SOL должно находиться два числа: минимальное и максимальное число кубиков, которые можно было бы использовать для построения фигуры с заданными проекциями.
Пример выходных данных
4 7
Решение g6_1055:
Сейчас я начал активные тренировки на украинских задачках. К ним прилагаются тесты, так что вы сможете проверить, насколько верно вы решили ее.
Разобьем изображения фигуры на вертикальные слои. Для нижнего слоя получим:
11 - вид спереди, 111 - вид справа.
Для минимального количества кубиков вид сверху будет выглядеть так:
100 010 001а для максимального так:
111 111 111Для того чтобы найти минимальное количество кубиков в слое достаточно среди количества кубиков во фронтальной и боковой проекции выбрать наибольшее. Действительно, если во фронтальной проекции лежит 4 кубика, а в боковой - 3, то мы можем выстроить 4 кубика так, что фронтальная проекция будет состоять из 4 кубиков, а боковая из 3. Если фигура имеет разрывы, то это никак не влияет на такое предположение. Пример для фронтальной проекции - 4(11101), боковой - 3(10101).
10000 00000 01100 00000 00001Как видно, здесь фигура проецируется в 11101 и 10101. Теперь посчитаем максимум для данных проекций.