Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Сумма делителей

Рекурсия

Для данного натурального числа n вычислите сумму всех его натуральных делителей, включая 1 и само число. Решение оформите в виде РЕКУРСИВНОЙ функции int SumOfTheDivisors (int n)

Ввод
6
Вывод
12

Как поделить картошку

Рекурсия

Вася и Петя пошли копать картошку. В конце дня они накопали N мешков с картошкой весом W1, W2, ... WN. Как им поделить мешки с картошкой между собой, чтобы разница масс была минимальной.

Входные данные
В первой строке  записано число N – количество мешков (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы мешков W1, W2 , … WN (1 ≤ Wi ≤ 105).
 
Выходные данные
В единственную строку нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух куч с мешками.

Ввод Вывод
5
5 3 5 7 8
2

Разложение на слагаемые

Рекурсия

Требуется вывести все различные представления натурального числа N в виде суммы натуральных чисел. Представления, отличающиеся друг от друга порядком слагаемых, не являются различными.
 
Входные данные
Входная строка содержит целое число N (2 ≤ N ≤ 40).
 
Выходные данные
В ответе выведите все различные представления числа N без повторов в виде суммы по одному на отдельной строке. Как слагаемые, так и сами суммы могут следовать в произвольном порядке.

Ввод Вывод
4
1+1+1+1
1+2+1
1+3
2+2
5
1+1+1+1+1
1+1+1+2
1+1+3
1+2+2
2+3
1+4

Скобки-2

Рекурсия

Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
 
Входные данные
В первой строке находится единственное число N. 1 <= N <= 14, N - чётное.
 
Выходные данные
Каждое выражение выводится в отдельной строке.

Ввод Вывод
2
()
[]
4
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]

Наибольшая строка

Рекурсия

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

Ввод Вывод
11111111 1

https://informatics.msk.ru/mod/statements/view3.php?id=26735&chapterid=113653#1

Звездочки

Рекурсия

Дана строка, содержащая только английские буквы (большие и маленькие). Добавить символ ‘*’ (звездочка) между буквами (перед первой буквой и после последней символ ‘*’ добавлять не нужно).
 
Входные данные
Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков.
 
Выходные данные
Вывести строку, которая получится после добавления символов '*'.

Ввод Вывод
LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO L*I*t*B*e*o*F*L*c*S*G*B*O*F*Q*x*M*H*o*I*u*D*D*W*c*q*c*V*g*k*c*R*o*A*e*o*c*X*O

https://informatics.msk.ru/mod/statements/view3.php?id=26735&chapterid=113655#1

Троечные последовательности

Рекурсия

Вводится число N. Сгенерируйте в анти-лексикографическом порядке все последовательности длины N, состоящие из чисел 3, 4, 5, в которых количество троек не превосходит двух.
 
В "анти-лексикографическом" обозначает "в порядке, обратном к лексигографическому" (см. пример).
 
В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.
В анти-лексикографическом, соответственно, наоборот.
 
1≤N≤10
 
Входные данные
3
 
Выходные данные
 
5 5 5
5 5 4
5 5 3
5 4 5
5 4 4
5 4 3
5 3 5
5 3 4
5 3 3
4 5 5
4 5 4
4 5 3
4 4 5
4 4 4
4 4 3
4 3 5
4 3 4
4 3 3
3 5 5
3 5 4
3 5 3
3 4 5
3 4 4
3 4 3
3 3 5
3 3 4

Перебор строк №3

Рекурсия

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию. 

Ввод Вывод
3
KKK
KLL
KMM
KNN
LKK
LLL
LMM
LNN
MKK
MLL
MMM
MNN
NKK
NLL
NMM
NNN
16


(c) К.Ю. Поляков
 

Заполнение конем

Рекурсия

Дана шахматная доска nхn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.
 
Входные данные
На вход программе подается натуральное число n (n8).
 
Выходные данные
Если обход невозможен, то выведите в выходной файл 0, если возможен, то 1, а на следующих строчках выведите матрицу nn, иллюстрирующую порядок обхода. Выравнивать числа по столбцам не обязательно.
 
Примечание. Скорость работы рекурсивной программы в этой задаче существенно зависит от порядка, в каком будут рассматриваться варианты хода коня из очередной клетки. Одним из удачных порядков является размещение всех восьми вариантов хода "по кругу".

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

Вычисление факториала

Рекурсия

Составить программу с рекурсивной функцией для расчета факториала.

Входные данные
В первой строке вводится натуральное число N (  N<=12 ).

Выходные данные
Выведите факториал числа.

Ввод Вывод
1 1
2 2



Перебор строк №2

Рекурсия

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв, в которых вторая буква «K». Подсчитайте количество таких слов. 

Ввод Вывод
2 KK
LK
MK
NK
4


(c)  К.Ю. Поляков

Сумма кубов

Рекурсия

Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.

Выяснилось, что почти все чиcла, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов.

Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.

Входные данные
Вводится натуральное число N <= 2*109.

Выходные данные
Требуется вывести не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.

Ввод Вывод
239 IMPOSSIBLE
17 2 2 1


Источник: https://informatics.msk.ru/mod/statements/view3.php?id=254&chapterid=158#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

Источник: https://informatics.msk.ru/mod/statements/view.php?id=254#

Произведение битов

Рекурсия

Составить программу с рекурсивной функцией для расчета произведения битов в натуральном числе.

Входные данные
В первой строке вводится натуральное число N (  N<=109 ).

Выходные данные
Выводите произведение битов.

Ввод Вывод
16 0
7 1



Сумма битов

Рекурсия

Составить программу с рекурсивной функцией для расчета суммы битов в натуральном числе.

Входные данные
В первой строке вводится натуральное число N (  N<=109 ).

Выходные данные
Выводите сумму битов.

Ввод Вывод
16 1
7 3



Количество цифр

Рекурсия

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

Ввод Вывод
74kz31n8pn26f2iv10c7u8x356gl73jlka67i929z08i5mnn35h0n 28
https://informatics.msk.ru/mod/statements/view3.php?id=26735&chapterid=113654#1

Двоечные последовательности

Рекурсия

Вводится число N. Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не превосходит 2-х.
 
В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.
 
1≤N≤10
 
Входные данные
3
 
Выходные данные
2 2 4
2 2 5
2 4 2
2 4 4
2 4 5
2 5 2
2 5 4
2 5 5
4 2 2
4 2 4
4 2 5
4 4 2
4 4 4
4 4 5
4 5 2
4 5 4
4 5 5
5 2 2
5 2 4
5 2 5
5 4 2
5 4 4
5 4 5
5 5 2
5 5 4
5 5 5

Функция

Рекурсия

Функция f с натуральными аргументами и значениями определена так:
 
f(0) = 0
f(1) = 1
f(2n) = f(n)
f(2n + 1) = f(n) + f(n + 1)
Составить программу вычисления f(n) по заданному n.

Входные данные
Дано одно число n (1 ≤ n ≤ 1018).
 
Выходные данные
Выведите f(n)

Ввод Вывод
10 3
https://informatics.msk.ru/moodle/mod/statements/view.php?chapterid=111599#1