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

Третья тренировка

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

Задача 3А.Разложение на простые множители

Вывести представление целого числа N в виде произведения простых чисел.
Ограничения: 2 $\le$ N$\le$ 2³¹ - 1, время 2 с.
Ввод из файла pfactor.in. В первой строке находится единственное число N Вывод в файл pfactor.out. Выводится список чисел в порядке неубывания, разделенных знаком «*».
Примеры
Ввод 5 Вывод  5
Ввод 30 Вывод 2*3*5

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

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

Задача 3С. Копилка

Заданы вес Е пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов; известны ценность Р_i, каждого вида монет и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 $\le$ Е $\le$ F$\le$ 10 000, 1 $\le$ N$\le$ 500, 1 $\le$ Р_i $\le$50 000, 1 $\le$ W_i $\le$ 10 000, все числа целые, время 2 с.
Ввод из файла piggy.in. В первой строке находятся числа E и F, во второй — число N, в следующих N строках — по два числа, Р_i и W_i.
Вывод файл piggy.out. Выводятся два числа через пробел — минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, — вывести This is impossible.
Примеры
Ввод 1
1000 1100
2
1 1
5 2
Вывод 1
100 250
Ввод 2
1000 1010
2
6 3
2 2
Вывод 2
10 16
Ввод 3
1000 2000
1
10 3
Вывод 3
This is impossible.

Задача 3D. Открытка и конверт

Даны размеры прямоугольных открытки и конверта. Требуется определить, поместится ли открытка в конверт.
Ограничения: размеры открытки и конверта — целые положительные числа, не превосходящие 100, время 1 с.
Ввод из файла postcard.in. В первой строке находятся размеры открытки, во второй — размеры конверта.
Вывод в файл postcard.out. Если открытку можно вложить в конверт, вывести «Possible», если нет — вывести «Impossible».
Пример
Ввод
1 10
9 9
Вывод
Possible

Задача 3E. Длинное произведение

Даны целые неотрицательные числа М и N. Найти М • N.
Ограничения: 0 $\le$ M, N$\le$ 10²⁵⁰⁰, время 5 с.
Ввод из файла longprod.in. В первой строке находится число М, во второй — N.
Вывод в файл longprod.out. Вывести одно число — результат умножения.
Пример
Ввод
9876543210
1023456789
Вывод
10108215200126352690

Задача 3F. Змейка

Вывести квадрат, состоящий из N x N ячеек, заполненных числами от 1 до N
«змейкой» (см. примеры).
Ограничения: 2 $\le$ N$\le$ 100, время 1 с.
Ввод из файла serpent.in. В первой строке находится единственное число N.
Вывод в файл serpent.out. Выводится N строк по N чисел, разделенных пробелами. Не допускается начинать змейку в ином, кроме верхнего левого, углу или задавать  ей другое направление.

Примеры
Ввод 3
Вывод

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