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

Пятая тренировка

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

Задача 5А. Дружественные числа

Два различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа, а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от М до N.
Ограничения: 1 $\le$M$\le$N$\le$ 1 000 000, все числа целые, время 1 с.
Ввод из файла friendly.in. В первой строке находятся числа М и N.
Вывод в файл friendly.out. В каждой строке вывести по паре чисел через пробел.Первое число нары должно быть меньше второго. Строки должны быть отсортированы в порядке возрастания первого числа пары. Если пар дружественных чисел в промежутке нет, вывести «Absent».
Примеры
Ввод
200 300
Вывод
220 284
Комментарий к примеру 1
220 = 1 + 2 + 4 + 71 + 142 (все делители числа 284);
284 = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 (вседелители числа 220).
Ввод
200 250
Вывод
Absent
Ввод
185000 205000
Вывод
185368 203432
196724 202444

Задача 5B. Скобки (2)

Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
Ограничения: 1 $\le$ N$\le$ 14, N - четное, время 2 с.
Ввод из файла bracket2.in. В первой строке находится единственное число N. Вывод в файл bracket2.out. Каждое выражение выводится в отдельной строке.
Пример
Ввод
4
Вывод
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]

Задача 5С. Маршрут (2)

Дана матрица NхN, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной К (клетку можно посещать несколько раз).
Ограничения: 2 $\le$ N$\le$ 100, элементы матрицы имеют значения от 1 до 9999,1 $\le$K$\le$< 2000, все числа целые, время 5 с.
Ввод из файла route2.in. В первой строке находятся разделенные пробелом числа N и К. Затем идут N строк по N чисел в каждой. Вывод в файл route2.out. Вывести одно число — максимальную сумму.
Пример
Ввод
5 7
1 1 1 1 1
1 1 3 1 9
1 1 6 1 1
1 1 3 1 1
1 1 1 1 1
Вывод
21

Задача 5D. Выпуклая оболочка

На плоскости заданы N точек своими декартовыми координатами. Найти минимальный периметр многоугольника, содержащего все эти точки. Гарантируется, что искомый многоугольник имеет ненулевую площадь.
Ограничения: 3 $\le$ N$\le$ 1000, -10 000 $\le$ х_i, у_i $\le$ 10 000, все числа целые, все точки различны, время 2 с.
Ввод из файла conhull.in. В первой строке находится число N, далее — N строк с парами координат. Вывод в файл conhull.out. Вывести одно число — длину периметра с одним знаком после запятой.
Пример
Ввод
5
1 0
0 1
-1 0
0 -1
0 0
Вывод
5.7

Задача 5E. Системы счисления

Дано целое неотрицательное число в I-ричной системе счисления. Вывести эточисло в J-ричной системе счисления.
Ограничения: 2 $\le$ I,J $\le$ 36, для представления цифр 10...35 используются прописные латинские буквы A...Z соответственно, число разрядов исходного числа не превышает 1000, время 5 с.
Ввод из файла scale.in. В первой строке находятся числа I и J(в десятичной системе счисления), во второй строке — число для перевода. Вывод в файл scale.out. Вывести искомое число. Если число начинается с буквы, перед ней не должно быть нуля.
Пример
Ввод
10 36
29234652
Вывод
HELLO

Задача 5F. День рождения

Заданы день и месяц рождения, а также текущие день, месяц и год. Определить, сколько дней осталось до дня рождения. Примечание. Високосные годы — это те, номер которых делится на 400, а также те, номер которых делится на 4, но не делится на 100.
Ограничения: год от 1920 до 3000, месяц — от 1 до 12, день — от 1 до числа дней в месяце, время 1 с.
Ввод из файла birthday.in. В первой строке находятся разделенные пробелами день и месяц рождения, во второй — разделенные пробелами текущие день, месяц и год. Вывод в файл birthday.out. Вывести число дней, оставшихся до дня рождения.
Примеры
Ввод
19 04
19 04
Вывод
0
Ввод
05 05
19 04 2002
Вывод
16
Ввод
29 02
28 02 2001
Вывод
1096

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