Тут у меня одна задачка которую никак не могу решить уже целую неделю. Главное не могу определиться с алгоритмом. Прошу вас помочь если сможете конечно. И так задано N чисел и требуеться найти минимальное число которое невозможно составить из сумм каких-либо заданных чисел. Но каждое заданное число можно использовать максимум один раз, т.е. можно и какое-то не использовать. Допустим если задано 1, 2, 4, 9, 100 то ответ будет 8. потому что 3 не может быть ответом так как 2+1=3, 5 тоже нет т.к. 4+1=5, и 7 т.к. 4+2+1=7, а вот 8 никак не получиться.

вот моя прога но она не совсем правильна.

var
 n,i,j:byte;
 d:array [1..100] of longint;
 cem:qword;
begin
 readln(n);
 for i:=1 to n do read(d[i]);
 if d[1]>1 then begin writeln(1); exit; end;
 i:=0;
 repeat
  inc(i); cem:=0;
  for j:=1 to i do cem:=cem+d[j];
  if cem+1<d[i+1] then begin writeln(cem+1); exit; end;
 until cem+1<d[i+1];
end.

кто нибудь знает где ошибка? может есть алгоритм получше? помогите пожалуйста.
заранее большое спасибо.

есть идея, тока она очень бредовая....
Заводишь массив, сортируешь, складываешь первые 2, если их сумма меньше след элемента, то его и выводишь,
если нет, то первый и 3-й, потом 4-й и 1-й, и так пока не найдешь или не будет конец массива....

Bard, у тебя алгоритм правильный.

Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 1. (т.е. на случай, когда cem+1<d[i+1] не выполнится никогда).

Твое решение можно ускорить: не считай сумму каждый раз, вместо этого накапливай ее в одной переменной.

Client, спасибо за помощь но помоему я сделал тоже самое . Не всегда правильно где-то есть ошибка а наверняка и алгоритм получше есть .

Ограничения есть? На скорость выполнения, например? Если нет (и максимальное число в списке из N чисел не превосходит 255) - то можно чуть-чуть переработать вот это: разложение числа и на приведенных тобой данных это выдаст правильный результат (проверил только что)...

Если есть ограничения - то говори, какие - ибо там рекурсия, соответственно о высокой скорости речи быть не может, и память будет жрать...

Ты сделал не то же самое. Client предлагает складывать не первые k, а первое и k-тое.

Добавлено через 1 мин.
Bard, покажи пример, на котором работает неправильно.

Да я это понял просто не сразу. Извиняюсь. Но в его алго ведь есть ошибка. вот например в этом примере 4+2+1=7 его алгоритм выдасть ошибку.


а вот этого я не понял. ты говоришь что сначала суммровать все а потом по одному отнимать или как?
ведь мне не сумма всех обязательно нужна.



ну только то что (1 ≤ N ≤ 100), (1 ≤ d[i] ≤ 1000000, d[i] < d[i+1]), время 1 секунда и ограничение памяти 16 МБ.

Кстати volvo спасибо за ссылку надеюсь поможет.

забудь что я сказал про ускорение. твой алгоритм и так достаточно быстрый.

volvo, я просмотрел ту ссылку и все понял, но осталось только одно. ведь каждое число разрешается использовать только один раз. как мне это сделать?

Bard, я же тебе сказал, твой алгоритм - правильный. И сказал, что нужно подправить. И спросил, на каком примере у тебя не работает. Ты меня игнорируешь?

Bard, можешь побольше примеров привести?

To Bard: вот так, например (сразу говорю, реализация очень неэффективна - только для ознакомительных целей, по заданным критериям явно не будет проходить, лучше доработай свой - там совсем немного осталось)

Нажмите для просмотра прикрепленного файла

эта здача с acm.timus.ru. я вот посылаю и проходит всего 3 теста ну вот поэтому я не знаю где у меня не проходит.



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


Добавлено через 15 мин.


можешь помочь? как мне написать это условие и куда мне его поставить? я не совсем понял что ты имеешь в виду...

Я тебе сказал про две вещи, обе про цикл:





Вторую забудь, т.к. решение и так быстрое. А первую сделай.

У тебя цикл кончается только если в какой-то момент cem+1 станет меньше d[i+1]. А если этого никогда не случится, что будет?

Например, тест 1 2 4 8.

Исправишь - сразу получишь АС.

Добавлено через 1 мин.


перед вот этой строкой:



проверь, что i < n. если i = n, выводи ответ (какой?) и выходи из цикла.

Все наконец-то ... Огромное тебе спасибо Michael_Rybak . Извини что сразу не послушал , просто хотелось побольше идей ...

а вот и код программы:
Нажмите для просмотра прикрепленного файла

Вот и отлично Поздравляю

Bard, а если вводиться 1 2 9 4 100 ответ тоже должен быть 8??

Client, там числа по возрастанию отсортированы.