Пакет 10. Перебор и способы его сокращения
В задачах, в которых выделены разделы «Входные данные» и «Выходные данные» предполагается, что данные считываются из текстового файла INPUT.TXT, а результат записывается в файл OUTPUT.TXT
1. Даны N целых чисел X1, X2, …, Xn. Расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному S.
Ограничения
2 ≤ N ≤ 24, 0 ≤ Xi ≤ 50 000 000, -1 000 000 000 ≤ S ≤ 1 000 000 000, время 3 с.
Входные данные
В первой строке находятся числа N и S. В следующей строке – N чисел через пробел
Выходные данные
Если получить требуемый результат невозможно, вывести «No solution», если можно – то вывести равенство. Если решение не единственное, вывести любое
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 3 10 15 25 30 | 15+25-30=10 |
2 | 2 100 10 10 | No solution |
2. Вывести все представления натурального числа N суммой натуральных чисел. Перестановка слагаемых нового способа представления не дает.
Ограничения
2 ≤ N ≤ 40, время 2 с.
Входные данные
В первой строке находится единственное число N.
Выходные данные
В каждой строке выводится одно из представлений. В сумме слагаемые разделяются знаком «+».
Пример
№ | INPUT. TXT | OUTPUT. TXT |
1 | 4 | 1+1+1+1 1+2+1 1+3 2+2 |
3. Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.
Время: 1 сек. Память: 16 Мб
Входные данные
Входной файл INPUT. TXT содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.
Выходные данные
В выходной файл OUTPUT. TXT следует вывести YES, если искомая перестановка цифр возможна, в противном случае необходимо вывести NO. При положительном ответе во второй строке следует вывести число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y при выводе не должны содержать ведущих нулей. Числа в строке разделены пробелом. Если решений несколько, то следует вывести ту пару, в которой число x минимально.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 12 31 25 | YES |
2 | 12 31 26 | NO |
3 | 101 2 13 | YES |
4. Обеденный перерыв Гомера Симпсона составляет T мс. Один гамбургер Гомер съедает за N мс, один чизбургер – за M. Требуется найти максимальное суммарное число гамбургеров и чизбургеров, которые Гомер может съесть в течение обеденного перерыва.
Ограничения
1 ≤ M, N,T ≤ 1 000 000, все числа целые, время 2 с.
Входные данные
В первой строке находится числа M, N, T, разделенные пробелами.
Выходные данные
Вывести максимальное суммарное число гамбургеров и чизбургеров. Если останется какое-то время, требуется указать его через пробел. Предпочтителен вариант, когда дополнительного времени остается как можно меньше.
Пример
№ | INPUT. TXT | OUTPUT. TXT |
1 | 3 5 54 | 18 |
2 | 3 5 55 | 17 |
3 | 4 4 6 | 1 2 |
