Тренировка S06

Время тестирования приведено для Intel Celeron 400.
Решения должны быть представлены на Turbo Pascal 7.0. Объём памяти, предоставляемый программе, составляет 500 кб.

        Задача A. Закраска прямой

На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.
Ограничения: Li и Ri - целые, -1 000 000 000 <= Li <= Ri <= 1 000 000 000, 1 <= N <= 15 000, время 1 с.
Ввод из файла cover.in. В первой строке находится число N, в следующих N строках - пары Li и Ri.
Вывод в файл cover.out. Вывести одно число - длину окрашенной части прямой.
Примеры 
Ввод 1    Ввод 2
2         1
1 3       10 10
2 4
Вывод 1   Вывод 2
3         0

        Задача B. Суммы

Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN.
Ограничения: 1 <= N <= 500, 0 <= Ai <= 100, 0 <= ki <= 1, все числа целые, время 2 с.
Ввод из файла sums.in. В первой строке находится число N, во второй - A1, A2, ..., AN через пробел.
Вывод в файл sums.out. Вывести одно число - количество различных значений сумм.
Примеры 
Ввод 1    Ввод 2    Ввод 3
3         3         5
1 1 2     1 3 2     49 100 98 49 0
Вывод 1   Вывод 2   Вывод 3
5         7         10

        Задача C. Игра "Даты"

Играют двое. Задаётся какая-то дата 2004 года. Каждый игрок на своём ходе называет более позднюю дату, увеличивая на 1 или 2 либо день в месяце, либо месяц, но не то и другое сразу. При этом сочетание дня и месяца должно оставаться датой. Игрок, назвавший 31 декабря, проигрывает. Оба играют наилучшим образом. Исходя из заданной даты вывести, кто выиграет.
Ограничения: месяц от 1 до 12, день от 1 до числа дней в месяце, даты "31 декабря" во входных данных нет, время 1 с.
Ввод из файла dategame.in. В первой строке находятся числа, обозначающие день и месяц.
Вывод в файл dategame.out. Вывести 1, если выигрывает первый (начинающий) игрок, или 2 - в противном случае.
Примеры 
Ввод 1    Ввод 2    Ввод 3
30 12     29 12     29 11
Вывод 1   Вывод 2   Вывод 3
2         1         2

        Задача D. Площадь прямоугольников

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.
Ввод из файла rectarea.in. В первой строке находится число прямоугольников - N. Затем идут N строк, содержащих по 4 числа: x1, y1, x2, y2 - координаты двух противоположных углов прямоугольника.
Ограничения: 1 <= N <= 100, координаты целые и по абсолютному значению не превосходят 10 000, время 3 с.
Вывод в файл rectarea.out. Вывести одно число - площадь фигуры.
Примеры 
Ввод 1
2
1 1 3 3
2 2 4 4
Вывод 1
7

        Задача E. Lines

В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.
Ограничения: 2 <= N <= 40, время 1 с.
Ввод из файла lines.in. В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика.
Вывод в файл lines.out. В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но буква X, а также все точки по пути заменяются плюсами.
Примеры 
Ввод 1    Ввод 2    Ввод 3
5         5         5
....X     ..X..     ...X.
.OOOO     .....     .....
.....     OOOOO     O.OOO
OOOO.     .....     .....
@....     ..@..     ....@
Вывод 1   Вывод 2   Вывод 3
Y         N         Y
+++++               ..++.
+OOOO               .++..
+++++               O+OOO
OOOO+               .++++
@++++               ....@

        Задача F. Покраска лабиринта

Лабиринт представляет собой квадрат, состоящий из NxN сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.
Ограничения: 3 <= N <= 33, размер сегмента 3 x 3 м, высота стен 3 м, время 1 с.
Ввод из файла paintlab.in. В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решётка - сегмент со стеной.
Вывод в файл paintlab.out. Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.
Примеры 
Ввод 1
5
.....
...##
..#..
..###
.....
Вывод 1
198