Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S. В первой строке находятся числа N и S. В следующей строке - N чисел через проб...
Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.
В первой строке находятся числа N и S. В следующей строке - N чисел через пробел. 2 <= N <= 24, 0 <= Xi <= 50 000 000, -1 000 000 000 <= S <= 1 000 000 000.
Если получить требуемый результат невозможно, вывести "No solution", если можно, то вывести равенство. Если решение не единственное, вывести любое.
Пример
входные данные:
3 13
7 3 9
выходные данные:
7-3+9=13
Ограничение по времени: 1 сек,
Ограничение по памяти: 64 мегабайта,
Язык программирования: PascalABC.NET.
Гость
Ответ(ы) на вопрос:
ГостьНиже запрограммировано примерно следующее: делим массив на 2 части (в каждой будет не больше 12 элементов), для каждой части вычисляем всевозможные суммы с плюсами-минусами. Затем для каждой суммы из левой части пытаемся найти бинпоиском сумму из правой части, чтобы получилось то, что надо. Если нашли - повторяем всё для каждой части и пытаемся восстановить ответ.
function getAllSums(myarr: array of integer): array of integer;
begin
var answer := arrFill(round(power(2, myarr.Length)), 0);
for var i := 0 to round(power(2, myarr.Length)) - 1 do
begin
var s := 0;
var k := i;
for var j := 0 to myarr.Length - 1 do
begin
if k mod 2 = 0 then s += myarr[j] else s -= myarr[j];
k := k div 2;
end;
answer[i] := s;
end;
result := answer;
end;
function getSolution(myarr: array of integer; s: integer): array of boolean;
begin
if myarr.Length = 1 then
begin
result := Arr(myarr[0] = s);
exit;
end;
var sums_left := getAllSums(myarr[:myarr.Length div 2]);
var sums_right := getAllSums(myarr[myarr.Length div 2:]).Sorted.ToArray;
for var i := 0 to sums_left.Length - 1 do
if sums_right.BinarySearch(s - sums_left[i]) >= 0 then
begin
result := getSolution(myarr[:myarr.Length div 2], sums_left[i]) +
getSolution(myarr[myarr.Length div 2:], s - sums_left[i]);
exit;
end;
result := new boolean[0];
end;
begin
var n := readinteger;
var s := readinteger;
var xn := readarrinteger(n).Select(x->abs(x)).ToArray;
var signs := getSolution(xn, s);
if signs.Length = 0 then
print('No solution')
else
begin
if signs[0] then
write(xn[0])
else
write('-', xn[0]);
for var i := 1 to xn.Length - 1 do
if signs[i] then
write('+', xn[i])
else
write('-', xn[i]);
write('=', s);
end;
end.
Не нашли ответ?
Похожие вопросы