Рекурсивный перебор Автоматизированная система генерации тестов

Твитнуть

Плюсануть

Класснуть

Запинить

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

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

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

В каком-то другом мире сегодня 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-битное целое число.

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

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

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

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

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

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

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

Ограничения

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

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

Очередь в душ

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

Много студентов живут в общежитии. Общежитие — это большой мир веселых развлечений и возможностей, но у него есть свои минусы.
В общежитии всего один душ, а желающих принять душ утром, конечно, больше. Поэтому каждое утро перед душем общежития образуется очередь из пяти человек.
Как только душ открывается, первый человек из очереди заходит в душ. Спустя некоторое время, когда первый зашедший выходит из душа, следующий заходит в душ. Этот процесс продолжается, пока все в очереди не примут душ.

Душ — дело не быстрое, поэтому во время ожидания студенты общаются. В каждый момент времени студенты общаются парами: (2*i - 1)-й человек в очереди (на текущий момент) общается с (2*i)-м.
Рассмотрим этот процесс подробнее. Обозначим людей цифрами от 1 до 5. Пусть изначально очередь имеет вид 23154 (человек 2 стоит в начале очереди). Тогда перед открытием душа 2 общается с 3, 1 общается с 5, 4 ни с кем не общается. Затем 2 заходит в душ. Пока 2 принимает душ, 3 и 1 общаются, а также 5 и 4 общаются. Затем 3 заходит в душ. Пока 3 принимает душ, 1 и 5 общаются, 4 ни с кем не общается. Затем 1 заходит в душ, а пока он принимает душ, 5 и 4 общаются. Затем 5 заходит в душ, а затем 4 заходит в душ.

Известно, что если студенты i и j общаются, то радость студента i увеличивается на g_i,j, а радость студента j увеличивается на g_j,i. Вам надо найти такой изначальный порядок студентов в очереди, чтобы суммарная радость всех студентов в итоге была максимальной. Стоит заметить, что некоторые студенты могут общаться несколько раз. В приведенном выше примере студенты 1 и 5 общаются пока ждут открытия душа, а также пока 3 принимает душ.

Сегодня возле душа выстроилась очередь ровно из 5 студентов. Найдите максимально возможную суммарную радость этих студентов.

Входные данные
Входные данные состоят из пяти строк, в каждой строке записано пять целых чисел разделенных пробелом: j-е число в i-й строке обозначает g_i,j (0 ≤ g_i,j≤ 10⁵). Гарантируется, что g_i,i = 0 для всех i.
Считайте, что студенты пронумерованы от 1 до 5.

Выходные данные
Выведите единственное целое число — максимально возможную суммарную радость студентов.

Задача о назначениях lite

Перестановки Перебор с возвратом Рекурсивный перебор

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

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где A_i,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех A_i,j выполнено 1 <= A_i,j <= 10⁵.

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

Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.

Все перестановки

Перестановки Перебор с возвратом Рекурсивный перебор

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

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

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

Королевское путешествие

Перестановки Простые задачи на перебор Гамильтонов цикл Гамильтонов цикл Перебор с возвратом Рекурсивный перебор

Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:

1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);

2) маршрут должен включать все населенные пункты ровно по одному разу (если король пропустит какой-то населенный пункт, то его жители будут возмущены королевским невниманием и перестанут платить налоги; если король посетит какой-то населенный пункт больше одного раза, то жители остальных населенных пунктов также возмутятся)

3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.

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

Входные данные
Сначала вводится число N (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует N строк по N чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.

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

Перестановки. Встроенные функции в С++ и Python

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

Задача в разработке

Числа с заданной суммой цифр

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

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

Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр, все цифры > 0)
Вторая строка: целевая сумма S (1 ≤ S ≤ 15)

Формат выходных данных
Все возможные числа с суммой цифр = S, каждое на отдельной строке. Числа выводить в лексикографическом порядке. Если решений нет, вывести "NO"

ПОДСКАЗКА:
Используй отсечение! Если текущая сумма уже больше S, дальше искать не нужно — это экономит время.

Все числа

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

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

Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр)
Вторая строка: длина числа N (1 ≤ N ≤ 4)

Формат выходных данных
Все возможные числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке (как в словаре).

ПОДСКАЗКА:
Это базовая задача на перебор. Откат здесь не нужен, достаточно рекурсивно перебрать все комбинации.

Числа без повторяющихся соседей

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

Даны цифры и длина числа N. Выведите все числа длины N, составленные из данных цифр, в которых никакие две соседние цифры не совпадают.

Формат входных данных
Первая строка: цифры через пробел (от 2 до 5 цифр)
Вторая строка: длина числа N (2 ≤ N ≤ 5)

Формат выходных данных
Все подходящие числа, каждое на отдельной строке. Числа выводить в лексикографическом порядке.

ОБЪЯСНЕНИЕ:
Числа 11, 22, 33 не подходят, так как соседние цифры одинаковые.

ПОДСКАЗКА:
Перед добавлением цифры проверяй, не равна ли она последней добавленной. Если равна — это отсечение, пропускаем эту ветку.

Перестановки

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

Дан набор различных цифр. Выведите все перестановки этих цифр, то есть все числа, в которых каждая цифра используется ровно один раз.

Формат входных данных
Одна строка: цифры через пробел (от 2 до 5 различных цифр)

Формат выходных данных
Все перестановки, каждая на отдельной строке. Выводить в лексикографическом порядке.

ПОДСКАЗКА:
Нужно отслеживать, какие цифры уже использованы. Используй множество (set) или список для отметки использованных цифр. При откате не забудь снять отметку!

Путь в лабиринте

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

Дан лабиринт в виде прямоугольной таблицы N×M. Символ '.' — проход, символ '#' — стена. Найдите количество различных путей из левого верхнего угла (0,0) в правый нижний угол (N-1, M-1).
Двигаться можно только вправо или вниз. Проходить через одну клетку дважды нельзя.

Формат входных данных
Первая строка: два числа N и M — размеры лабиринта (2 ≤ N, M ≤ 5)
Следующие N строк: лабиринт (символы '.' и '#')

Формат выходных данных
Одно число — количество различных путей.
Если путей нет, вывести 0.

Примечание

В тестовом примере существуют два пути
Путь 1: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
Путь 2: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

ПОДСКАЗКА:
1. Отмечай посещённые клетки, чтобы не ходить по кругу
2. При откате снимай отметку о посещении
3. Проверяй границы лабиринта и стены

Подмножества с заданной суммой

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

Дан набор различных положительных чисел и целевая сумма S. Найдите все подмножества, сумма элементов которых равна S. Каждое число можно использовать не более одного раза.

Формат входных данных
Первая строка: числа через пробел (от 2 до 8 чисел)
Вторая строка: целевая сумма S

Формат выходных данных
Все подмножества с суммой S, каждое на отдельной строке. Числа в подмножестве выводить через пробел в порядке возрастания. Подмножества выводить в лексикографическом порядке. Если решений нет, вывести "NO"

Примечание

В тестовом примере возможны только две комбинации
2+3+5=10
3+7=10
Другие комбинации не дают сумму 10.

ПОДСКАЗКА:
Для каждого числа есть два варианта: взять его или не взять. Используй отсечение: если текущая сумма уже больше S, дальше искать не нужно.

Размен монет

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

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

Важно: наборы, отличающиеся только порядком монет, считаются одинаковыми! Например, 1+2 и 2+1 — это один способ.

Формат входных данных
Первая строка: номиналы монет через пробел (от 1 до 5 монет)
Вторая строка: сумма S (1 ≤ S ≤ 20)

Формат выходных данных
Одно число — количество способов размена.

Примечание

В тестовом примере способы разменять 4:

1+1+1+1
1+1+2
2+2

Всего 3 способа.

ПОДСКАЗКА:
Чтобы избежать повторений (1+2 и 2+1), перебирай монеты в определённом порядке: каждая следующая монета должна быть не меньше предыдущей.

Монетки

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

В Волшебной стране используются монетки достоинством A₁, A₂,..., A_M. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы сначала поступает число N (1 <= N <= 10⁹), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A₁, A₂,..., A_M (1 <= A_i <= 10⁹).

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

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

Ввод	Вывод
100 6 11 20 30 40 11 99	3 40 30 30