Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Интересные разбиения#50575

Недавно на кружке по математике Миша узнал про разбиения на слагаемые. Разбиением числа \(n\) на слагаемые называется представление его в виде суммы неубывающего набора натуральных чисел. Например, \(9=1+2+2+4\) является разбиением числа 9 на слагаемые.

Миша называет разбиение интересным, если никакие два слагаемых в наборе не равны и не отличаются ровно на 1. Так, например, разбиение, приведенное выше не является интересным, а разбиение \(9=1+3+5\) — является.

Помогите Мише вывести все интересные разбиения числа \(n\) на слагаемые.

Формат входных данных
На ввод подается одно целое число \(n\) (\(1 \le n \le 80\)).

Формат выходных данных
Выведите все интересные разбиения числа \(n\) на слагаемые. Разбиения можно выводить в любом порядке. Соблюдайте формат из примера.

Рекурсия

✓ 7✗ 2—Войти и решать

Непростые разбиения#50276

Рассмотрим разбиения целого положительного числа \(n\) в сумму целых положительных чисел. Будем называть разбиение непростым, если слагаемые в нем упорядочены по неубыванию, причем среди слагаемых нет простых чисел.

Например, для \(n=5\) существует два непростых разбиения: \(1+1+1+1+1\) и \(1+4\).

Задано число \(n\). Выведите все его непростые разбиения на слагаемые.

Формат входных данных
На вход подается число \(n\) (\(1 \le n \le 70\)).

Формат выходных данных
Выведите все непростые разбиения \(n\) на слагаемые. Слагаемые разделяйте знаком <<+>>. Не выводите пробелы. Разбиения можно вывести в любом порядке.

Динамическое программирование Рекурсия

✓ 14✗ 32800средняяВойти и решать

Все сочетания из n по k#47937

Даны два целых числа n и k, выведите все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Порядок элементов в одной комбинации не важен. То есть комбинация (1, 2, 3) и (3, 2, 1) считается одинаковой.
Выведите на экран все такие комбинации в лексикографическом порядке.

Входные данные
В первой строке записано целое число n, во второй - целое число k.

Ограничения

1 <= n <= 20
1 <= k <= n

Выходные данные
Выведите в лексикографическом порядке все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Каждая комбинация чисел должна выводиться в отдельной строке, числа в одной комбинации разделяются одним пробелом.

Перебор с возвратом Рекурсия

✓ 61✗ 50700средняяВойти и решать

XOR-cумма массива#47936

XOR-cумма массива определяется как побитовое XOR всех его элементов или 0, если массив пуст.

Например, XOR-сумма массива [2,5,6] равна 2 XOR 5 XOR 6 = 1.
Для заданного массива nums, верните сумму всех XOR-сумм для каждого подмножества nums.

Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз.
Массив a является подмножеством массива b, если a может быть получено из b путем удаления некоторых (возможно не удалением никаких) элементов b.

Входные данные
Программа получает на вход в первой строке натуральное число n - количество элементов массива nums. Во второй строке записаны n чисел nums_i.

Ограничения

1 <= n <= 12
1 <= nums_i <= 20

Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом примере
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Перебор с возвратом Рекурсия

✓ 73✗ 48800средняяВойти и решать

Задача Магистра Математикуса#46766

Магистр Математикус обладает волшебными способностями, которые позволяют ему превращать положительные числа в 1 с помощью следующих операций:

Если число четное, он может разделить его на 2.
Если число нечетное, он может увеличить его на 1 или уменьшить на 1.

Сегодня Магистр Математикус задумался над вопросом, какое минимальное количество операций ему необходимо выполнить для превращения числа n в 1 с использованием его волшебных способностей. Помогите ему ответить на этот вопрос.

Входные данные
Программа получает на вход целое число n.

Ограничения на входные данные

1 <= n <= 2³¹ - 1

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	8	3
2	7	4

Рекурсия

✓ 16✗ 39700средняяВойти и решать

Перевод числа в десятичную систему счисления (рекурсивно)#46615

Напишите программу, которая переводит число N из системы счисления с основанием r в десятичную систему счисления.

Входные данные
Программа получает на вход два натуральных числа: N и r (2 <= r <= 9). Гарантируется, что число N является правильной записью числа в системе счисления c основанием r (то есть содержит цифры от 0 до r-1).

Выходные данные
Выведите на экран число в десятичной системе счисления.

Примеры

№	Входные данные	Выходные данные
1	`100 2`	`4`

Информатика Рекурсия Системы счисления

✓ 224✗ 527600лёгкаяВойти и решать

Степень двойки (рекурсивно)#46614

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.

Операцией возведения в степень пользоваться нельзя!

Входные данные

Вводится натуральное число N (N < 10⁹).

Выходные данные

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1	YES
2	4	YES
3	5	NO

Рекурсия

✓ 119✗ 123400лёгкаяВойти и решать

+3 or +5#43329

Маленький Гриша научился выполнять с любым числом две операции: прибавлять к числу 3 и прибавлять к числу 5. Но, к сожалению, он еще не знает, что таким путем он не cможет из числа 1 получить любое число. Помогите Грише понять, сможет ли он из числа 1 получить число N или нет.

Входные данные

Программа получает на вход натуральное число N (N <= 200).

Выходные данные

Выведите слово YES, если число N можно получить из числа 1, или NO - в противном случае.

Примечание

Число 1 можно получить всегда, не выполняя при этом никаких действий.

Примеры

№	Входные данные	Выходные данные
1	5	NO
2	1	YES

Рекурсия

✓ 157✗ 297500лёгкаяВойти и решать

Все ПСП#39370

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

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

Выходные данные
Выведите все правильные скобочные последовательности по возрастанию в лексикографическом порядке. Каждую в отдельной строке.

Динамическое программирование Перебор Перебор с возвратом Рекурсия

✓ 221✗ 198700средняяВойти и решать

Счастливого Нового Года!#38924

В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня L (L - целое число, большее или равное 0) готовится следующим образом:

Бургер нулевого уровня - это котлета.
Бургер с уровнем L (L >= 1) - это булочка, бургер с уровнем (L-1), котлета, бургер с другим уровнем (L-1) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.

Например, бургер уровня 1 и бургер уровня 2 выглядят как БКККБ и ББКККБКБКККББ (повернутые на 90 градусов), где Б и К обозначают булочку и котлету.

Бургер, который приготовит дед Кокованя, - это бургер уровня N. Дарёна всегда съедает только Х слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?

Входные данные
Программа получает на вход 2 целых числа через пробел: N и X (1 <= N <= 50, 1 <= X <= (общее количество слоев в бургере N-го уровня)).

Выходные данные
Выведите количество котлет в самых нижних X слоях, считая от нижней части бургера уровня N.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 7	4	В самых нижних 7 слоях бургера второго уровня ( `ББКККБКБКККББ`) находятся 4 котлеты.
2	1 1	0
3	50 4321098765432109	2160549382716056	Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число.

Перебор Рекурсивный перебор Рекурсия

✓ 38✗ 2571 000средняяВойти и решать

Площадь комнаты#38638

Требуется вычислить площадь комнаты в квадратном лабиринте.

Входные данные
В первой строке вводится число N – размер лабиринта (3 <= N <= 10). В следующих N строках задан лабиринт (‘.’ – пустая клетка, ‘*’ – стенка). И наконец, последняя строка содержит два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и что лабиринт окружен стенками со всех сторон.

Выходные данные
Требуется вывести единственное число – количество пустых клеток в данной комнате.

Примеры

№	Входные данные	Выходные данные
1	5 *** ..* ..* ..* ***** 2 4	3

Обход в глубину Рекурсия

✓ 59✗ 108700средняяВойти и решать

Разбиение на невозрастающие слагаемые, лексикографический порядок#38609

Дано натуральное число N. Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.

Входные данные
Задано единственное число N. (N ≤ 40)

Выходные данные
Необходимо вывести все разбиения числа N на натуральные слагаемые в лексикографическом порядке.

Примеры

№	Входные данные	Выходные данные
1	5	1 1 1 1 1 2 1 1 1 2 2 1 3 1 1 3 2 4 1 5

Разбиения Рекурсия

✓ 43✗ 54900средняяВойти и решать

XOR и сумма#38518

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

Битовые операции Динамическое программирование Рекурсия

✓ 1✗ 1—Войти и решать

Взвешивание#38318

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

Входные данные
Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

Выходные данные
В первой строке выведите веса гирек, которые нужно поместить на левую чашу весов, во второй строке — гирьки, которые нужно поместить на правую чашу. Если на какую-то чашу ни одной гирьки помещать не нужно — выведите в этой строке число 0. Если с помощью данных гирек привести весы в равновесие нельзя, выведите одно число –1. Если вариантов несколько, выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	5 2 3 5	0 5
2	5 3 6 3 4	4 3 6
3	5 1 2	-1

Перебор Рекурсия

✓ 14✗ 261 100средняяВойти и решать

Перебор строк №1#37810

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

Рекурсивный перебор Рекурсия

✓ 1✗ 3—Войти и решать

Быстрое возведение в степень#33680

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
\(a^n=(a^2)^{n/2},\ при \ четном \ n, \\ a^n=a \cdot a^{n-1},\ при \ нечетном \ n.\)

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .

Входные данные
Программа получает на вход вещественное число a и целое число n (a > 0, 0 <= n <= 10⁹). Каждое число в отдельной строке.

Выходные данные
Выведите \(a^n\) с точностью не менее 5 знаком после запятой.

Примеры

№	Входные данные	Выходные данные
1	2 7	128
2	1.00001 100000	2.71827

Рекурсия

✓ 2 304✗ 10 133500лёгкаяВойти и решать

Число сочетаний#33679

По данным числам n и k (0<=k<=n) вычислите \(С_n^k\) . Для решения используйте рекуррентное соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^k\).

Решение оформите в виде функции C(n, k).

Входные данные: Вводятся целые числа n и k.

Выходные данные: Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	4 2	6

Задачи на процедуры и функции Комбинаторика Рекурсия

✓ 2 904✗ 4 901400лёгкаяВойти и решать

Максимум последовательности#33647

Напишите рекурсивную функцию, которая вычисляет максимальное значение из последовательности целых чисел, поданных не её вход. Ввод заканчивается числом 0. Основная программа должна содержать вызов функции и вывод результата. Запрещено использовать циклы

Входные данные: Во входных строках записаны целые числа, по одному в каждой строке. В последней строке записано число 0.

Выходные данные: Программа должна вывести одно число – максимальное значение из всех элементов последовательности (не считая числа 0).

Примеры

№	Входные данные	Выходные данные
1	1 3 2 0	3

Рекурсия

✓ 153✗ 236500лёгкаяВойти и решать

Сумма элементов последовательности#33646

Напишите рекурсивную функцию, которая вычисляет сумму элементов последовательности целых чисел, поданных не её вход. Ввод заканчивается числом 0. Основная программа должна содержать вызов функции и вывод результата. Запрещено использовать циклы

Выходные данные: Программа должна вывести одно число – сумму всех элементов последовательности.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 0	6

Рекурсия

✓ 298✗ 263500лёгкаяВойти и решать

Только квадраты#33645

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

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

Примеры

№	Входные данные	Выходные данные
1	1 2 3 4 0	4 1

Рекурсия

✓ 30✗ 240800средняяВойти и решать