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

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

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

Задача 2А. Простые числа (2)

Вывести все простые числа от М до N включительно.
Ограничения: 2 $\le$M$\le$N$\le$ 1 000 000, время 6 с.
Ввод из файла primes2.in. В первой строке находятся разделенные пробелом М и N.
Вывод в файл primes2.out. Вывести числа в порядке возрастания, по одному в строке. Если между М и N включительно нет простых — вывести «Absent».
Примеры
Ввод 2 5 Вывод 2 3 5
Ввод 4 4 Вывод Absent

Задача 2B. Перестановки

Дана строка, состоящая из М попарно различных символов. Вывести все перестановки символов данной строки.
Ограничения: 2 $\le$ М $\le$ 8, символы — буквы латинского алфавита и цифры, время 1 с.
Ввод из файла permut.in. В первой строке файла находится исходная строка.
Вывод в файл permut.out. Вывести в каждой строке файла по одной перестановке.
Перестановки можно выводить в любом порядке. Повторений и строк, не являющихся перестановками исходной, быть не должно.
Примеры
Ввод AB  Вывод AB BA

Ввод IOX
Вывод 2
XOI
OIX
IXO
XIO
OX1
IOX

Задача 2С. Маршруты

В таблице из N строк и N столбцов клетки заполнены цифрами от 0 до 9. Требуется найти такой путь из клетки (1, 1) в клетку (N, N), чтобы сумма цифр в клетках, через которые он пролегает, была минимальной; из любой клетки ходить можно только вниз или вправо.
Ограничения: 2 $\le$N$\le$ 250, время 1 с.
Ввод из файла route.in. В первой строке находится число N. В следующих N строках содержатся по N цифр без пробелов.
Вывод в файл route.out. Выводятся N строк по N символов. Символ «решетка» (#) показывает, что маршрут проходит через эту клетку, а минус — что не проходит. Если путей с минимальной суммой цифр несколько, вывести любой.
Пример
Ввод
3
943
216
091
Вывод
#--
###
--#

Задача 2D. Пересечение отрезков

Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат. Требуется определить, существует ли у них общая точка.
Ограничения: координаты целые и по модулю не превосходят 10 000, время 1 с.
Ввод из файла segments.in. В первой строке содержатся координаты первого конца первого отрезка, во второй — второго конца первого отрезка, в третьей и четвертой — координаты концов второго отрезка.
Вывод в файл segments.out. Выводится слово «Yes», если общая точка есть, или слово «No» — в противном случае.
Примеры
Ввод 1
0 0
1 0
1 0
1 1
Вывод 1
Yes
Ввод 2
0 0
1 0
2 0
3 0
Вывод 2
No

Задача 2E. Длинная сумма

Даны два целых неотрицательных числа, М и N. Найти их сумму.
Ограничения: 0 $\le$ M, N< 10³⁰⁰⁰⁰ время 1 с.
Ввод из файла longsum.in. В первой строке содержится М, во второй — N.
Вывод в файл longsum.out. В первой строке вывести сумму без пробелов и ведущих
нулей.
Пример
Ввод
12345678901234567890123456789
1111111111111111111111111111
Вывод
13456790012345679001234567900

Задача 2F. Спираль

Вывести квадрат, состоящий из NхN клеток, заполненных числами от 1 до N² по
спирали (см. примеры).
Ограничения: 2 $\le$ N$\le$ 100, время 1 с.
Ввод из файла spiral.in. В первой строке находится единственное число N.
Вывод в файл spiral.out. Выводится N строк по N чисел, разделенных пробелами.
Не допускается начинать спираль в ином, кроме верхнего левого, углу, закручивать спираль против часовой стрелки или изнутри наружу.
Примеры
Ввод 1
3
Вывод 1
1 2 3
8 9 4
7 6 5
Ввод
4
Вывод

1	2	3	4
12	13	14	5
11	16	15	6
10	9	8	7

Ввод:
5
Вывод

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

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