ОЛИМПИАДНЫЕ ЗАДАНИЯ ◊	Олимпиадные задачи с рекомендациями к решениям

Задача 66: Кубики (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

Решение:
Сейчас я начал активные тренировки на украинских задачках. К ним прилагаются тесты, так что вы сможете проверить, насколько верно вы решили ее.
Разобьем изображения фигуры на вертикальные слои. Для нижнего слоя получим:
11 - вид спереди, 111 - вид справа.
Для минимального количества кубиков вид сверху будет выглядеть так:

100
010
001
 

а для максимального так:

111
111
111
 

Для того чтобы найти минимальное количество кубиков в слое достаточно среди количества кубиков во фронтальной и боковой проекции выбрать наибольшее. Действительно, если во фронтальной проекции лежит 4 кубика, а в боковой - 3, то мы можем выстроить 4 кубика так, что фронтальная проекция будет состоять из 4 кубиков, а боковая из 3. Если фигура имеет разрывы, то это никак не влияет на такое предположение. Пример для фронтальной проекции - 4(11101), боковой - 3(10101).

10000
00000
01100
00000
00001
 

Как видно, здесь фигура проецируется в 11101 и 10101. Теперь посчитаем максимум для данных проекций.
Если во фронтальной проекции на некоторой позиции стоит 1, то 1 могут быть заняты все клетки, кроме тех, которые соответствуют 0 в боковой проекции. Т.е. для одной единицы во фронтальной проекции получаем наибольшее количество блоков RB (кол-во единиц в боковой проекции), а так как у нас FB (кол-во единиц во фронтальной проекции) рядов, то максимальное кол-во блоков для слоя RB * FB. Чтобы посчитать максимальное количество блоков для всей фигуры достаточно просто сложить произведения RB на FB для всех слоев.
Технически это реализуется с помощью двух одномерных массивов, с номерами от 1 до n. В первом из них будет храниться количество элементов фронтальной и боковой проекции.

Далее ð