Во всех задачах этого листка необходимо реализовать перебор с возвратом. Общая схема перебора с возратом такая:
алг Перебор (Ситуация) нач если Ситуация конечная то Завершающая обработка иначе нц для любого возможного действия Применить действие к Ситуация Вызвать алгоритм Перебор(Ситуация) откатить действие назад кц все кон
Решите обычную задачу о расстановке ферзей на доске n×n в ограничениях n≤13. Используйте схему перебора с возвратом с отсечением невозможных ходов.
Ввод | Вывод |
---|---|
8 |
92 |
Грузоподъемность машины \(M\) килограмм. Есть \(n\) ящиков с грузами, масса \(i\)-го ящика равна \(m_i\). Определите, какую наибольшую массу грузов можно увезти на автомашине.
Программа получает на вход действительное число \(M\), затем количество ящиков \(n\le 20\), затем \(n\) действительных чисел: массы ящиков.
Программа должна вывести единственное число: максимальную массу, которую можно увезти на машине. Выводите число с точностью в 15 знаков.
Ввод | Вывод |
---|---|
10 |
9 |
1073.15936137 |
1064.0876642466 |
На плоскости даны \(N\) точек. Соедините их замкнутой ломаной линией минимальной длины.
Программа получает на вход число \(N\le10\). Далее идет \(N\) пар действительных чисел: координаты точек.
Выведите одно действительное число: минимальную длину замкнутой ломаной, проходящей через все эти точки. Ответ выводите с точностью в 15 знаков.
Ввод | Вывод |
---|---|
4 |
4.82842712474619 |
Решите задачу B в ограничениях n≤27;. Используйте следующие оптимизации:
Решите задачу C в ограничениях n≤12. Используйте следующую оптимизацию:
Дано выражение: \[a_1 ? a_2 ? ... ? a_n = S\]
Посчитайте, сколькими способами в этом выражении можно заменить вопросительные знаки на знаки операций сложения и умножения так, чтобы выполнялось равенство.
Программа получает на вход число n (n≤26) и S (1≤S≤106). Далее идет n натуральных чисел ai, также не превосходящих 106.
Выведите одно число — количество расстановок знаков сложения и умножения, дающих верное равенство.
Ввод | Вывод |
---|---|
2 4 |
2 |