Два различных натуральных числа n и m называются дружественными, если сумма делителей числа n (включая 1, но исключая само n) равна числу m и наоборот. Например, 220 и 284 – дружественные числа. По данному числу k выведите все пары дружественных чисел, каждое из которых не превосходит k.
Программа получает на вход одно натуральное число k, не превосходящее 105.
Программа должна вывести все пары дружественных чисел, каждое из которых не превосходит k. Пары необходимо выводить по одной в строке, разделяя пробелами. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает).
300
220 284
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Программа получает на вход одно натуральное четное число n (3<n<2*105).
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.
4
2 2
6
3 3
| Максимальное время работы на одном тесте: | 2 секунды |
Даны два натуральных числа N и K. Требуется вывести все цепочки x1, x2, ..., xN такие, что xi - натуральное и 1 ≤ xi ≤ K.
Вводятся два натуральных числа N и K (N, K ≤ 6).
Выведите все требуемые цепочки в произвольном порядке – по одной на строке. Никакая цепочка не должна встречаться более одного раза.
2 3
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
| Максимальное время работы на одном тесте: | 1 секунда |
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
На вход программы сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.
Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
100 6 11 20 30 40 11 99
3 40 30 30
| Максимальное время работы на одном тесте: | 1 секунда |
Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
- Издевается! - подумал Борман.
- Кольцевая! - догадался Штирлиц.
В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...
Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.
В первой строке задается число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.
Требуется вывести три числа — номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.
5 0 1 9 9 2 1 0 9 9 9 9 9 0 9 9 9 9 9 0 9 2 9 9 9 0
1 2 5