Задачи первого тура олимпиады школьников УР по информатике в 1997 г.

ЗАДАЧА N1 - "Гвозди"

  В длинную деревянную рейку вбили несколько гвоздей Некоторые пары гвоздей связываются веревочками так, Чтобы выполнялись следующие условия:

1. к каждому гвоздю была привязана хотя бы одна веревочка;
2. суммарная длина веревочек была бы минимально возможной.

ЗАДАНИЕ:

  Написать программу, которая связывает пары гвоздей веревочками как описано выше.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ:

  Входными данными (файл TEST1.DAT) являются число гвоздей (не более 1000) и их координаты (целые числа в диапазоне от 0 до 1 000 000 000), выходными (файл TEST1.RES) - минимальная суммарная длина и пары номеров соединяемых гвоздей.

Пример входных данных	Пример выходных данных
5	3
11	1	2
12	2	3
13	4	5
16
17

Максимальная оценка - 20 баллов.

ЗАДАЧА N2 - "Головоломка"

  Квадрат размером 5x5 вдоль линий сетки разбили на несколько фигурок. Написать программу, которая определяет, можно ли переложить часть фигурок так, чтобы снова образовался квадрат размером 5x5. При перекладывании НЕ разрешается поворачивать и переворачивать фигурки.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ:

  Входные данные - символьная матрица размером 5x5 (пять строк в файле TEST2.DAT). Каждая буква в матрице означает идентификатор фигурки, содержащей соответствующую клетку. Идентификаторами являются большие буквы латинского алфавита. Программа должна выдать (в файл TEST2.RES) другой способ составления квадрата размером 5x5, либо, если такого способа нет, то слово "НЕТ".

Пример входных данных	Пример выходных данных
EEEEE	EEEEE
EBEEE	EAEEE
ABCCE	BAAAE
AAADE	BAAAE
AAAEE	DCCEE

Максимальная оценка - 30 баллов.

ЗАДАЧА N3 - "Острова"

  В плоском океане расположен архипелаг из N островов, каждый из которых имеет форму многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальна.

ЗАДАНИЕ:

  Напишите программу, находящую описанное соединение.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ:

  Входными данными (файл TEST3.DAT) являются число островов в архипелаге(N)и N описаний островов. Каждый остров задается числом вершин и их координатами в порядке обхода по часовой стрелке. Программа должна вывести два числа - количество мостов и их суммарную длину.

Пример входных данных					Пример выходных данных
3					2	2.000
4	0 0	0 1	1 1	1 0
4	2 0	2 1	3 1	3 0
3	4 0	5 1	5 0

Максимальная оценка - 50 баллов.

Задачи второго тура олимпиады школьников УР по информатике в 1997 г.

ЗАДАЧА N4 - "Строчки"

  Заданы две символьные строки A и B. Требуется вычислить, сколькими способами можно получить строку B из строки A, вычеркивая некоторые символы. Например, если A и B имеют соответственно вид *Самарина Ирина* и *Сара*, то искомое число равно 7, а для строк *aaabbbbccc* и *abc*, это число равно 36.

ЗАДАНИЕ:

  Напишите программу, находящую требуемое число способов.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

  Входные строки подаются в файле TEST4.DAT.

Максимальная оценка - 30 баллов.

ЗАДАЧА N5 - "Многоугольник"

  Многоугольник на плоскости задан целочисленными координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих:

1. на границе многоугольника (включая вершины);
2. строго внутри него.

ЗАДАНИЕ:

  Напишите программу, вычисляющую требуемое количество точек для двух заданных случаев.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ:

  Входными данными (файл TEST5.DAT) являются число вершин многоугольника (не более 1000) и их координаты в порядке обхода по часовой стрелке. Координаты вершин - целые числа и по модулю не превосходят 1 000 000.

Пример входных данных				Пример выходных данных
4				80
-10	-10	-10	10	361
10	10	10	-10

Максимальная оценка - 30 баллов.

ЗАДАЧА N6 - "Змея"

  Змея - фигура из N клеток, все клетки которой можно обойти ходом шахматной ладьи. Ладье при этом запрещено проходить по одной клетке дважды и проходить по соседним клеткам, если она не пересекает границу между этими клетками. Для заданного N в общем случае может существовать несколько различных змей. Фигуры, совпадающие при переносах и (или) поворотах (а также при переворачивании), различными не считаются.

Пример змеи:   **         Не является змеей фигура: ***

              * *                                    **

              ***

ЗАДАНИЕ:

  Написать программу, которая находит все различные змеи из N клеток.

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ:

 Число N вводиться с клавиатуры. Программа должна вывести общее количество различных змей, содержащих N клеток.

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

Максимальная оценка - 40 баллов.