Олимпиада по программированию

Архив задач в формате MS-WORD: Скачать [16048 байт, архив WinRar].

Имена входных файлов ко всем задачам - INPUT.TXT.
Имена выходных файлов у всех задач - OUTPUT.TXT.

ЗАДАЧИ:

Задача A. Слоники.
Время работы на одном тесте: 5 секунд

Расставьте на шахматной доске N x N минимальное количество слонов так, чтобы они били все поле (любая клетка должна находиться на одной диагонали хотя бы с одним слоном).

Формат входных данных:

В файле записано единственное целое число 0 <= N <= 1000.

Формат выходных данных:

На первой строке выведите минимальное количество слонов.

Строки с номерами 2...N + 1 содержат описание доски, 0 - соответствующая клетка пуста, 1 - в клетке стоит слон. Числа необходимо разделять пробелами.

Примеры:

2

2
0 0
1 1

Задача B. Единицы и нули.
Время работы на одном тесте: 10 секунд

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

Формат входных данных:

На первой строке записано нечетное число 1 <= N <= 101. На следующих N строках находится описание листа.

Формат выходных данных:

K-ая строка выходного файла описывает k-ое действие: она должна содержать N чисел, среди которых i-ое число является номером столбца, выбранной в i-ой строке клетки. Количество действий не должно превосходить 100 000. В конце файла выведите -1.

На первой строке выведите минимальное количество слонов.

Примеры:

3
1 1 1
1 1 0
1 1 1

3 1 2
1 2 3
-1

1 1 0
0 1 0
1 0 1

0 1 0
0 0 0
1 0 0

Задача C. Многоугольники.
Время работы на одном тесте: 5 секунд

Назовем суммой двух многоугольников А и В множество всех точек плоскости с координатами (x, y), для которых существуют такие точки (x1, y1) и (x2, y2), принадлежащие соответственно А и В, что x = x1 + x2 и y = y1 + y2. Суммой выпуклых многоугольников является выпуклый многоугольник. Во входном файле дано описание двух выпуклых многоугольников, найдите их сумму.

Формат входных данных:

В первой строке записано количество вершин многоугольника 3 <= N <= 100. На следующих N строках находятся координаты вершин в порядке обхода против часовой стрелки. Далее в том же формате описывается второй многоугольник. Все числа во входном файле целые и по абсолютной величине не превосходят 10000.

Формат выходных данных:

В описанном выше формате выведите сумму многоугольников. Вершины должны следовать в порядке обхода против часовой стрелки, никакие две соседние стороны не могут лежать на одной прямой.

Примеры:

3
0 0
2 0
1 2
4
0 0
2 0
2 2
0 2

6
0 0
4 0
4 2
3 4
1 4
0 2

Задача D. Факториал.
Время работы на одном тесте: 1 секунда

N! = 1 * 2 * 3 ... * N.

Вычислите остаток от деления N! на N + 1.

Формат входных данных:

На первой строке входного файла записано число 1 <= N <= 2 000 000 000.

Формат выходных данных:

Выведите остаток от деления N! на N + 1.

Примеры:

3

2

Задача E. Длинное число.
Время работы на одном тесте: 5 секунд

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

Формат входных данных:

На первой строке записано натуральное число в десятичной системе счисления, количество цифр которого не превосходит 200 000.

Формат выходных данных:

Выведите число, получившееся после вычеркивания цифры.

Примеры:

121

11

5

0

Задача F. Промежутки.
Время работы на одном тесте: 1 секунда

Найдите объединение двух промежутков.

Формат входных данных:

Первая и вторая строки описывают промежутки: [a,b] - отрезок от a до b, (a,b) - интервал от a до b, [a,b) или (a,b] - полузамкнутые интервалы. -10000 <= a, b <= 10000. Ни один из промежутков не является пустым множеством. Пробелы между числами, скобками и запятыми отсутствуют. Все числа во входном файле целые.

Формат выходных данных:

Если объединение можно записать в виде одного промежутка, выведите этот промежуток. Если нет, выведите два промежутка в формате $a,b$ + $c,d$, a < c - здесь знак $ обозначает соответствующую скобку - [, ], ( или ). Пробелы между числами, скобками и запятыми необязательны.

Примеры:

[10,20]
[15,30]

[10, 30]

(3,4)
(1,2)

(1, 2) + (3, 4)

Задача G. Сумма.
Время работы на одном тесте: 10 секунд

Во входном файле записаны целые неотрицательные числа. Найдите минимальное целое неотрицательное число, которое нельзя представить в виде суммы этих чисел (каждое число можно использовать не более одного раза).

Формат входных данных:

На первой строке записано количество чисел 1 <= N <= 10000. На второй строке находятся сами числа.

Формат выходных данных:

Выведите искомое число.

Примеры:

3
1 2 5

4

Задача H. Простой факториал.
Время работы на одном тесте: 10 секунд

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

Формат входных данных:

На первой строке записано натуральное число, количество цифр в котором не превосходит 5000.

Формат выходных данных:

Если данное число является разностью простых факториалов А и В (А > В), то выведите А. Если нет, то выведите -1.

Примеры:

4

3

3

-1

Комментарий:
4 = 2 * 3 - 2
Число 3 не является разностью простых факториалов.

Задача I. Эффект бабочки.
Время работы на одном тесте: 1 секунда

Во дворе находятся две круглые клумбы, устройство которых позволяет им пересекаться. Бабочка летит по прямой и хочет, чтобы ее путь имел ровно одну общую точку с каждой из клумб. Каким образом можно исполнить ее желание?

Формат входных данных:

В первой строке записаны координаты центра и радиус одной клумбы, на второй - координаты центра и радиус другой. Все числа целые и не превосходят по модулю 1000000.

Формат выходных данных:

На первой строке выведите количество различных путей. Если таких путей бесконечно много, выходном файле должно быть выведено единственное число -1. Будем задавать прямую уравнением a x + b y = c. Следующие строки должны содержать по три коэффициента - a, b и c, - описывающих прямые. Ответ будет проверяться с точностью до четырех знаков после запятой.

Примеры:

0 0 1
1 0 1

2
0 1 1
0 1 -1

0 3 100
0 3 100

-1