Задача 3. парк (80 баллов)

ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ

Муниципальный этап, 2015-2016 учебный год

Задачи для 9-11 классов

Задача 1. Дизайнер (40 баллов)

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

Требуетсянаписать программу, которая определяет площадь не закрашенной части.

Описание входных данных

Входные данные вводятся с клавиатуры или из файла input.txt.

Первая строка входного файла INPUT.TXT содержит два натуральных числа W и H (1 ≤ W, H ≤ 1000). Во второй строке записано целое число N (0 ≤ N ≤ 10 000) – количество прямоугольников. Следующие N строк содержат информацию о всех прямоугольниках. Каждая строка описывает один прямоугольник в виде четырех чисел x1, y1, x2, y2 , где (x1, y1) и (x2, y2) – координаты левого верхнего и правого нижнего угла прямоугольника соответственно.

Описание выходных данных

Выходные данные выводятся на экран или в файл output.txt.

Выведите в выходной файл OUTPUT.TXT одно целое число – площадь не закрашенной части холста.

Примеры входных и выходных данных

Входные данные	Выходные данные
5 5 2 1 1 3 3 2 2 4 4
6 7 3 0 0 5 5 1 1 4 4 2 2 3 3

Задача 2. Подземелья гномов (80 баллов)

В подземелья гномов горы Рона спрятаны несметные сокровища. Но только отважные золотоискатели способны пройти все испытания и добыть сокровища гномов. Потому что подземелье гномов размером разделено на n*m квадратов, и в каждом квадрате нужно пройти испытание. Испытания разные и каждое имеет свой вес А(i,j). Испытания необходимо минимизировать.

Требуетсянаписать программу перехода из точки (1,1) в точку (n,m) при условии, что можно пройти из какой-либо клетки в любую из 3-х соседних, стоящих в строке и/или столбце с номером на 1-цу большем (см. рисунок).

Описание входных данных

Первая строка входного файла INPUT.TXT содержит два натуральных числа n и m (1 ≤ n, m ≤ 100). Следующие n строк содержат по m разделенных пробелом значений – вес испытания.

Описание выходных данных

Выведите в выходной файл OUTPUT.TXT одно целое число – сумму все испытаний, пройденных на пути.

Примеры входных и выходных данных

Входные данные	Выходные данные
2 3 1 1 3 2 4 2
6 3 0 2 3 1 1 1 3 2 1 5 3 2 1 1 1 2 2 3

Задача 3. Парк (80 баллов)

В городе Энске проектируют новый парк. Парк имеет форму правильного n-угольника. Дорожки в парке планируют проложить по диагоналям, причем никакие три не пересекаются в одной точке. В каждой полученной части парка решили поставить фонтан.

Требуетсянаписать программу подсчитывающую, какое количество фонтанов будет установлено в парке города Энска. Диагонали заданы номерами вершин n-угольника, которые они соединяют, все вершины перенумерованы по порядку числами 1, ..., n. Отсчет вершин по часовой стрелке.