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

дана последовательность чисел в количестве 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

И всёж с отрицательными числами неясно.
Выходит надо тупо проверять все числа от единицы, на предмет того - не являются ли они суммой каких-то чисел последовательности.
Сортировка, я так понимаю, вообще ничего не даёт

Да, с отрицательными числами не проходит.

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

http://algolist.ru/olimp/rec_prb.php
задачи 5, 6 вроде похожи

Числа натуральные и отсортированы по неубыванию. Вот оно как!

Цитата

1. C[i+1]<S+2. Тогда понятно, что продавец может вернуть любую сдачу от 1 до C[i+1]+S, т.к. любая из этих сумм представима либо первыми i купюрами, либо (i+1)-ой купюрой вместе с некоторыми из первых i купюр.

2. C[i+1]>S+1. Тогда понятно, что продавец не может вернуть сдачу S+1.

(2) - текущая сумма S +1 меньше следующего слагаемого C[i+1] - S+1 нельзя разложить в сумму.
(1) - текущая сумма S +1 больше либо равна следующего слагаемого C[i+1], значит,
текущая сумма S +2 строго больше C[i+1].
(Это я для schooler'а, которому мое решение не показалось заслуживающим доверия )

К решению следует добавить предварительную проверку на наличие в массиве 1 и 2. Если их нет, то ничего искать не нужно.

спасибо! все понятно, вопрос решен.

schooler, одно исправление!!!

Цитата

предварительную проверку на наличие в массиве 1 и 2.

Только на единицу! Ведь у нас могут быть повторяющиеся единицы.

А зачем? Начать сразу с суммы нуля элементов, которая равна 0, 0+1 = 1, и с единицей сразу вопрос решится. Да и с двойкой тоже

Цитата amk @ 16.12.08, 19:46

А зачем? Начать сразу с суммы нуля элементов, которая равна 0, 0+1 = 1, и с единицей сразу вопрос решится. Да и с двойкой тоже

Да, действительно. Тем более, что считаем в цикле и сумму обнуляем.