задача про сумму

дана последовательность чисел в количестве N (N<100000). задача - найти минимальное натуральное число, которое нельзя представить в виде суммы некоторых чисел из последовательности (взятых только по одному разу). помогите её решить.

Сумму как понимать?
Если число совпадает с одним числом из последовательности, но не разлагается в сумму других чисел?

А какой диапазон чисел, входящих в последовательность?

Сортируем последовательность. Находим минимальное число x. Если в последовательности нет 1, то это число x+1.
Если есть 1, но нет 2, то это x+2...
Так, это неверно. Число x+k не является решением, если k разлагается в сумму меньших слагаемых...

Тривиальный случай. Если в последовательности нет 1 или 2, то это число 1 или 2.
Значит, последовательность выглядит 1, 2, ..., N.
Рассуждаем дальше. Если нет 3, то нельзя получить 4.
Вообщем, нужно подумать...

Сообщение отредактировано: Swetlana - 13.12.08, 14:52

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

Если даже сортировать нельзя, (ИМХО) тогда задача имеет чудесное гениальное решение...

Цитата schooler @ 13.12.08, 14:59

процесс затягивается на долго

4 секунды - это долго?

4 секунды? это как это?

Ну явно не пузырьком. Хотя бы так:

#include <iostream>
#include <list>
#include <ctime>
using namespace std;
 
int main()
{
    list<int> nums;
    for (int i = 0; i < 100000; i++)
        nums.push_back(rand());
 
    time_t t1 = time(0);
 
    nums.sort();
 
    time_t t2 = time(0);
 
    return 0;
}

На олимпиаде наверно нужно быструю сортировку самому писать.

Сообщение отредактировано: Der_Meister - 13.12.08, 15:23

Вот, заметила закономерность.
Последовательность отсортирована, следует найти минимальное число, которое не совпадает ни с одним членом последовательности и не разлагается в сумму.
Пример 1.
1, 2, 5, 6.
Суммируем непрерывную последовательность с шагом 1. 1+2=3. Добавляем еще 1. 3+1=4.
4 < 5, значит 4 получить нельзя.
Пример 2.
1,2,3,6.
1+2+3=6. 6+1=7. 7>6, значит 7 получить можно. Аналогично можно получить любое число 1...1+2+3+6.
Значит, минимальное число сумма всех членов последовательности + 1=13.

ну например, 1 2 3 4 11 или элементы повторяются.

Цитата

ну например, 1 2 3 4 11

И что???
1+2+3+4=10. 10+1=11. 11 уже присутствует в последовательности, т.е. допускает разложение в сумму (иначе 1 была бы ответом).
В данном примере можно получить все суммы от 1..21 = 1+2+3+4+11.
Ответ: 22.
О наличии повторяющихся элементов я еще не думала.
Если все элементы различны, то в каждом месте, где последовательность с шагом 1 прерывается, вычисляем сумму всех элементов от 1 до разрыва, прибавляем единицу. Если это меньше следующего члена последовательности, то все. Ответ - сумма+1.

ЗЫ. Повторяющиеся элементы ничего не меняют. Точно так же считаем сумму, добавляем 1 и сравниваем со следующим членом последовательности.

Доказывается мат. индукцией по числу "разрывов".
1. Проверяется случай одного "разрыва".
1,2, ..., k, k+x, k+x+1,...,k+n.
Числа могут повторяться. Их однократность нигде не используется.
C помощью чисел 1...k можно получить все числа 1...s=(1+...+k).
Если s<k+x, то s является минимальным.
Если s>=k+x, то можно получить все числа 1...s1=(1+...+k + k+x +...+k+n).
s1+1 является минимальным.
2. Индуктивное предположение для m разрывов.
3. Аналогично доказывается для m+1 разрыва.

Сообщение отредактировано: Swetlana - 13.12.08, 17:25

А из условия как-то явно не следует, что числа не могут быть отрицательными

Суммируем все отрицательные числа, получаем сумму -|s2|.
Если s<k+x-|s2|, то s является минимальным.
Если s>=k+x-|s2|, то можно получить все числа 1...s1=(1+...+k + k+x +...+k+n).

ЗЫ. А еще числа могут быть не целыми...

Сообщение отредактировано: Swetlana - 13.12.08, 17:37

Цитата Swetlana @ 13.12.08, 14:27

Сортируем последовательность. Находим минимальное число x. Если в последовательности нет 1, то это число x+1.

Сорь, тогда это число 1