Олимпиады

М.С. Густокашин,
Москва

За три года беспрерывной работы артель золотоискателей “Вперед, к коммунизму!”, состоящая из трех человек, добыла N самородков. Несмотря на то что до конца вахты оставался еще целый год, один из золотоискателей решил уехать — на Большой земле у него родился сын.

Оправдывая свое название, артельщики решили выдать отъезжающему ровно третью часть добытого золота. Несмотря на то что они скрашивали досуг решением математических головоломок, выбрать такой набор оказалось совсем непростой задачей, и последние дни артель простаивала, так как вместо добычи золота артельщики занимались его дележом. Вам надо написать программу, которая находит набор самородков, вес которого составляет третью часть от веса всего добытого золота, либо определить, что это невозможно.

Формат входных данных

Во входном файле записано целое число N — количество добытых самородков (1 N 500). Далее записано N целых чисел Mi (1 M_i 1000) — веса добытых самородков.

Формат выходных данных

Если набор составить возможно, то в первой строке выведите K — количество самородков в наборе, а затем K чисел, задающих номера самородков, входящих в набор. Если существует несколько ответов, то выведите любой из них.

Если набор составить невозможно, то выведите число 0.

Решение

Эта задача является вариацией на тему классической дискретной задачи “о рюкзаке”.

Во-первых, если сумма весов всех самородков не делится нацело на 3, то следует вывести ответ 0 и больше ничего не делать. Если это не так, то задача решается методом динамического программирования. Сначала запишем веса всех самородков в массив w.

Далее задачу будем решать последовательным добавлением самородков с запоминанием, кучи какого веса мы можем получить. Сначала имеется только куча весом ноль, не содержащая самородков. Если у нас всего один самородок, то варианта всего два: либо куча весом 0, либо куча весом M₁, состоящая только из первого самородка. При добавлении второго самородка у нас, в общем случае, оказывается уже 4 возможных варианта составления кучи, их веса могут быть такими: 0, M₁, M₂, M₁ + M₂. Аналогично можно продолжать и для большего количества самородков.

Несложно заметить, что несколько куч из разных наборов самородков могут иметь один и тот же вес (это видно уже для двух самородков, если их веса совпадают M₁ = M₂). Нам же важно узнать сам факт возможности составления кучи заданного веса и иметь возможность восстановить хотя бы один вариант составления такой кучи. При составлении решения надо следить за ситуациями, чтобы один и тот же самородок не участвовал в составлении кучи дважды.

Сначала решим более простую задачу: определим, возможно ли из заданного набора составить кучу требуемого веса и сколько самородков потребуется для этого. После небольшой модификации мы сможем восстанавливать решение.

Обозначим за S сумму весов всех самородков, деленную на 3. Максимальное значение, которое может принимать S, равно 1000 • 500 / 3 = 166 666.

Заведем массив от 0 до S: индекс в этом массиве будет означать вес текущей кучи самородка, сам массив (назовем его num) будет хранить количество использованных в этой куче самородков. Вначале заполним его признаками того, что такую кучу составить вообще невозможно (например, поместив в каждый элемент –1), кроме нулевого элемента, в который поместим 0.

Далее будем идти циклом по всем самородкам (текущий самородок будет иметь номер j) и пытаться добавить его ко всем существующим кучам (вес текущей кучи обозначим за i). Если получим из уже существующей кучи (вес i) и очередного самородка (вес w[j]) кучу с таким весом, который нельзя было составить из предыдущих самородков (num[i + w[j]] = -1), то запомним, что такую кучу составить можно и количество самородков в ней на 1 больше, чем в куче с весом i, к которой мы прибавляли очередной самородок (num[i + w[j]] =
= num[i] + 1). Реализовать такой метод можно с помощью прохода по массиву num с помеченными существующими кучами — если для текущего индекса в массиве записано неотрицательное число (кучу с весом i + w[j] можно составить из самородков с меньшими номерами), то проверяем элемент массива, индекс которого больше текущего на вес очередного самородка.

Рассмотрим пример массива num:

Содержимое этого массива означает, что мы можем составить кучу весом 0 из 0 самородков, весами 1 и 3 из 1 самородка и весом 4 из 2 самородков. Кучи других весов составить невозможно.

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

После того, как мы рассмотрим все самородки, мы можем сказать, можем ли мы составить кучу требуемого веса S (если num[S] = -1, то ее составить нельзя) и определить необходимое для ее составления количество самородков (это число хранится в num[S]). Заметим, что мы можем рассматривать не все самородки, в случае, если на каком-либо шаге num[S] будет отличаться от –1 (куча требуемого веса уже составлена и дальнейшее рассмотрение не обязательно).

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

Проиллюстрируем содержимое массивов num и used для первого теста из примера по шагам (номерам обрабатываемых самородков):

На 4-м шаге мы уже смогли составить кучу заданного веса и прерываем работу цикла по самородкам. Количество самородков для составления требуемой кучи равно 3.

Теперь будем восстанавливать номера самородков. Нам известно, что для составления кучи весом S последним был добавлен самородок с номером used[S]. То есть мы можем вывести этот номер и продолжить восстановление номеров для кучи уже без этого самородка (т.е. для кучи весом S-w[used[S]]). Этот процесс необходимо продолжать до тех пор, пока S не станет равным нулю.

Приведем исходный текст программы на Delphi/FreePascal (эта задача неразрешима 16-битными компиляторами, так как требует более 64 Кб памяти под массивы). В данном решении не используются отсечения в том случае, если требуемая куча уже составлена, а честно перебираются все самородки (что никак не влияет на ответ). Обратите внимание, как перебираются уже существующие кучи: начало и конец интервала перебора подобраны так, чтобы избежать выхода за пределы массива.

var

w : array[1..500] of integer;

used, num : array[0..166666] of longint;

i, j, k, n, s : longint;

begin

assign(input, 'input.txt');

reset(input);

assign(output, 'output.txt');

rewrite(output);

read(n);

s := 0;

for i := 1 to n do begin

read(w[i]); // считываем веса

s := s + w[i]; // считаем сумму

end;

// на троих поровну не делится

if s mod 3 <> 0 then writeln(0)

else begin

s := s div 3; // считаем долю одного

for i := 1 to s do

// заполняем -1 (никакие кучи составить

// невозможно)

num[i] := -1;

num[0] := 0; // кроме кучи веса 0

for j := 1 to n do // перебираем самородки

// перебираем все веса

for i := s - w[j] downto 0 do

if (num[i] <> -1) and (num[i + w[j]] < 0)

then begin

// нашли такую кучу, которая вместе

// с нашим самородком дает новую кучу

num[i + w[j]] := num[i] + 1;

// запоминаем, кто последний

used[i + w[j]] := j;

end;

// нельзя составить кучу

if num[s] = -1 then writeln(0)

// требуемого веса

else begin // а здесь - можно

// выводим количество самородков в куче

writeln(num[s]);

// и все самородки, пока куча не опустеет

while s <> 0 do begin

write(used[s], ' ');

s := s - w[used[s]]

end

end

end;

close(output)

end.