Формат выходных данных
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел разделенных пробелами, - одно из возможных построений.
Пример
input.txt
|
output.txt
|
5 4
1 3
1 4
4 3
5 2
|
Yes
5 2 1 4 3
|
Применим алгоритм топологической сортировки.
Занятие 14. Рекурсия - 2. Перебор.
Существует класс задач, в которых необходимо выбрать по какому-то критерию один из конечного числа вариантов. Для их решения можно перебрать все варианты и выбрать из них тот, который отвечает заданному критерию. Зачастую это удобно делать с помощью рекурсивных методов.
Например, в задаче нужно выбрать из N чисел K с максимальной суммой.В этом случае можно перебрать все возможные комбинации К чисел из заданных N и на каждом шаге проверять, является ли сумма текущей комбинации больше, чем ранее найденный максимум.
Эту задачу, конечно, можно решить гораздо проще, отсортировав числа по невозрастанию и взяв из них К первых, но бывают задачи, которые не имеют решения, отличного от переборного.
Задача 14-1. Монетки
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
1 секунда
|
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.
Формат входных данных
Во входном файле записано сначала число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).
Формат выходных данных
В выходной файл выведите сначала K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.
Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
Пример
input.txt
|
output.txt
|
5 2
1 2
|
3
1 2 2
|
7 2
1 2
|
-1
|
5 2
3 4
|
0
|
Представим N в виде суммы слагаемых вида AK*bK, где АK - достоинство монеты с номером K, а bK - количество монет с таким достоинством. По условию задачи 0<=bK<=2, значит всего вариантов 3M. Перебрать эти варианты можно с помощью рекурсивного алгоритма, заметив, что если мы возьмем bM монет достоинства АM, то задача сведется к аналогичной, где используются монеты достоинствами A1, A2,..., AM-1 и требуется набрать сумму N-AM*bM.
Задача 14-2. Сумма кубов
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
5 секунд
|
Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.
Выяснилось, что почти все чиcла, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов.
Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.
Формат входных данных
Натуральное число N <= 2*109.
Формат выходных данных
Не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.
Пример
input.txt
|
output.txt
|
17
|
2 2 1
|
239
|
IMPOSSIBLE
|
Обозначим задачу нахождения разложения числа N в сумму K кубов натуральных чисел (N,K).Тогда для того, чтобы решить исходную задачу, нужно найти такое число X, что (N-X3,K-1) имеет решение. Задача свелась к аналогичной меньшей размерности, значит, возможно ее решение рекурсивным методом.
Задача 14-3. Резисторы
Имя входного файла
|
input.txt
|
Имя выходного файла
|
output.txt
|
Максимальное время работы на одном тесте:
|
3 секунды
|
Радиолюбитель Петя решил собрать детекторный приемник. Для этого ему понадобился конденсатор емкостью C мкФ. В распоряжении Пети есть набор из n конеденсаторов, емкости которых равны c1, c2, ... ,cn соответственно. Петя помнит, как вычисляется емкость параллельного соединений двух конденсаторов (Cnew = C1 + C2) и последовательного соединения двух конеденсаторов ( Cnew = (C1*C2)/(C1+C2) ). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора конеденсаторов, такую, что ее емкость ближе всего к искомой (то есть абсолютная величина разности значений минимальна). Разумеется, Петя не обязан использовать для изготовления схемы все конденсаторы.
Напомним определение последовательно-параллельной схемы.Схема, составленная из одного конденсатора, - последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, - последовательно-параллельная, а также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, - последовательно-параллельная.
Формат входных данных
В первой строке каждого входного файла заданы числа n и C. Во второй строке содержится последовательность емкостей имеющихся в наличии конеденсаторов с1, с2, ..., сn. Значения всех емокостей - вещественные числа. Для всех входных файлов n < 7.
Формат выходных данных
В выходной файл необходимо вывести емкость такой схемы, емкость которой меньше всего отличается от C. Результат выводите с шестью знаками после запятой.
Пример
input.txt
|
output.txt
|
3 1.66
1 2 1
|
1.666666
|
Пояснение к примеру: последовательно соединим первый и второй конденсаторы, а затем полученную схему соединим параллельно с третьим.
Каждую пару конденсаторов из набора попробуем сначала заменить на их последовательное соединение, а затем на их параллельное соединение. Для полученного набора из n-1 конденсатора решим задачу рекурсивно.
|