10930. А - последовательность

А – последовательностью называется такая последовательность чисел a_i, что 1 £ a₁ < a₂ < … < a_n и каждый член a_k не является суммой двух или более разных предыдущих членов последовательности. В задаче следует установить, является ли входная последовательность А – последовательностью.

Вход. Первое число каждой строки содержит количество элементов последовательности n, 2 £ n £ 30. Далее в строке идет сама последовательность из n чисел. Известно, что 1 £ a_i £ 100.

Выход. Для каждого теста в первой строке вывести его номер и саму последовательность. Вторая строка должна содержать фразу о том, является ли входная последовательность А – последовательностью.

Пример входа

2 1 2

3 1 2 3

10 1 3 16 19 25 70 100 243 245 306

Пример выхода

Case #1: 1 2

This is an A-sequence.

Case #2: 1 2 3

This is not an A-sequence.

Case #3: 1 3 16 19 25 70 100 243 245 306

This is not an A-sequence.

РЕШЕНИЕ

последовательность

Анализ алгоритма

Поскольку n £ 30 и a_i £ 100, то достаточно построить все возможные суммы из чисел последовательности a_i. Эти суммы не больше 30 * 100 = 3000. Пусть уже рассмотрены числа {a₁, …, a_i-1} входной последовательности. Тогда положим m[s] = 1, если число s представляется в виде суммы некоторого подмножества {a₁, …, a_i-1} и m[s] = 0 иначе. При рассмотрении числа a_i (i = 1, …, n) должны выполняться условия: m[a_i] = 0 (a_i не является суммой некоторого подмножества предыдущих чисел) и a_i+1 > a_i (входная последовательность должна быть строго возрастающей). Далее для всякого s, для которого m[s] = 1, следует положить m[s + a_i] = 1. После чего m[s] = 1, если число s представляется в виде суммы некоторого подмножества {a₁, …, a_i}.

Пример

Второй тест не будет А – последовательностью, так как третий элемент равен сумме первого и второго: 3 = 1 + 2. Третий тест не будет А – последовательностью, потому что 19 = 3 + 16.

Реализация алгоритма

Заведем массив m длины MAX = 30 * 100 + 1 = 3001, в котором положим m[i] = 1, если число i представляется в виде суммы некоторого подмножества {a₁, …, a_n} и m[i] = 0 иначе. В массиве Numbers хранится сама последовательность a_i.

#define MAX 3001

int m[MAX], Numbers[31];

Переменная cs содержит номер теста.

cs = 1;

while(scanf("%d",&n) == 1)

{

Изначально положим m[i] = 0, m[0] = 1. Читаем входную последовательность в массив Numbers.

memset(m,0,sizeof(m)); m[0] = 1;

for(i = 0; i < n; i++)

scanf("%d",&Numbers[i]);

Последовательно обрабатываем числа a₁, a₂, …, a_n. Если для текущего числа Numbers[i] значение m[Numbers[i]] равно 1, то Numbers[i] представимо в виде суммы некоторых предыдущих чисел. Поскольку А - последовательность является строго возрастающей, то должно выполняться неравенство Numbers[i – 1] < Numbers[i], i = 1, 2, …, n – 1.

for(i = 0; i < n; i++)

{

if (m[Numbers[i]]) break;

if (i > 0 && Numbers[i-1] >= Numbers[i]) break;

Если m[j] = 1 и текущим рассматривается число Numbers[i], то в виде суммы первых i + 1 элементов (нумерация массивов начинается с нуля) будет представимо число j + Numbers[i]. То есть следует положить m[j + Numbers[i]] = 1. При этом массив m следует просматривать справа налево в поиске таких j, для которых m[j] = 1.

for(j = MAX - Numbers[i]; j >= 0; j--)

if (m[j]) m[j+Numbers[i]] = 1;

}

В первой строке выводим номер теста и саму последовательность.

printf("Case #%d:",cs++);

for(j = 0; j < n; j++) printf(" %d",Numbers[j]);

Во второй строке выводим информацию о том, является ли входная последовательность А – последовательностью. Оператор break в цикле обработки последовательности сработает, если на некотором шаге встретится число, которое не может быть продолжением А – последовательности. Таким образом, если a_i не является А – последовательностью, то будут обработаны не все числа и будет выполняться неравенство i < n. Выводим результирующее сообщение.

printf("\nThis is ");

if (i < n) printf("not ");

printf("an A-sequence.\n");

}