Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Шестая тренировка

содержание задачника

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

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

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

Дано N целых чисел A₁, A₂, ..., A_N. Требуется найти количество различных значений сумм вида k₁A₁+k₂A₂+...+k_NA_N.
Ограничения: 1 $\le$ N $\le$ 500,0 $\le$ A_i $\le$ 100, 0 $\le$ k_i $\le$ 1, все числа целые, время 2 с.
Ввод из файла sums.in. В первой строке находится число N, во второй — A₁, A₂, ..., A_N через пробел. Вывод в файл sums.out. Вывести одно число — количество различных значений сумм.
Примеры
Ввод
3
1 1 2
Вывод
5
Ввод
3
1 3 2
Вывод
7
Ввод
5
49 100 98 49 0
Вывод
10

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

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

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

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.
Ввод из файла rectarea.in. В первой строке находится число прямоугольников — N. Затем идут N строк, содержащих по 4 числа: x₁, y₁, х₂, у₂ - координаты двух противоположных углов прямоугольника.
Ограничения: 1 $\le$ N $\le$ 100, координаты целые и по абсолютному значению не превосходят 10 000, время 3 с. Вывод в файл rectarea.out. Вывести одно число — площадь фигуры.
Пример
Ввод
2
1 1 3 3
2 2 4 4
Вывод
7

Задача 6E. Lines

В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Ограничения: 2 $\le$ N$\le$ 40, время 1 с.
Ввод из файла lines.in. В первой строке находится число N, в следующих N строках — по N символов. Символом точки обозначена свободная клетка, латинской заглавной 0 — шарик, @ — исходное положение шарика, который должен двигаться, латинской заглавной X — конечное положение шарика.
Вывод в файл lines.out. В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов — как и на вводе, но буква X, а также все точки по пути заменяются плюсами.
Примеры
Ввод
5
....Х
.0000
.....
0000.
@....
Вывод
Y
+++++
+0000
+++++
0000+
@++++

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

Лабиринт представляет собой квадрат, состоящий из N x N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесен сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (рис. 6.1). Помогите ему рассчитать количество краски, необходимой для этого.
Ограничения: 3 $\le$ N$\le$33, размер сегмента 3 х 3 м, высота стен 3 м, время 1 с.
Ввод из файла paintlab.in. В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решетка — сегмент со стеной.
Вывод в файл paintlab.out. Вывести одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.

Пример
Ввод
5
.....
...##
..#..
..###
.....
Вывод
198

содержание задачника