1071. Несоставляемое число

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

Вход. В первой строке находится число n (1 ≤ n ≤ 10000), в следующих n строках – по одному натуральному числу в пределах от 1 до 10⁹.

Выход. Вывести требуемое минимальное несоставляемое число.

Пример входа 1	Пример выхода 1
4 1 1 1 5	4
Пример входа 2	Пример выхода 2
4 1 2 4 8	16

РЕШЕНИЕ

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

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

Пусть m₁, m₂, …, m_n – отсортированная последовательность входных чисел.

Пусть s_k = . Если s_k + 1 < m_k+1, то число s_k + 1 не представимо в виде суммы элементов массива m. Если для всех k (0 £ k < n) выполняется неравенство s_k + 1 < m_k+1, то искомым числом будет s_n + 1, где n – размер массива a.

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

Входную последовательность чисел храним в массиве m.

#define MAX 10000

int m[MAX];

Читаем входную последовательность чисел.

scanf("%d",&n);

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

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

Сортируем массив.

sort(m,m+n);

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

{

if (m[i] > s + 1) break;

s += m[i];

}

Выводим ответ.

printf("%lld\n",s + 1);