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

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

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

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

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

Примечание

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

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

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

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

Примечание

ID 89118. Размен монет

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

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

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

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

Примечание

• 1+1+1+1
• 1+1+2
• 2+2

ID 89117. Перестановки

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

ID 89114. Все числа

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

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

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


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

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

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

ID 39369. Очередь в душ

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

Душ — дело не быстрое, поэтому во время ожидания студенты общаются. В каждый момент времени студенты общаются парами: (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 увеличивается на gi,j, а радость студента j увеличивается на gj,i.  Вам надо найти такой изначальный порядок студентов в очереди, чтобы суммарная радость всех студентов в итоге была максимальной. Стоит заметить, что некоторые студенты могут общаться несколько раз. В приведенном выше примере студенты 1 и 5 общаются пока ждут открытия душа, а также пока 3 принимает душ.

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

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

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

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

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

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

Примеры

ID 31794. Монетки

В Волшебной стране используются монетки достоинством 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 (минус один).