задача на динамику или же перебор Опции

[Bard]

Тут у меня одна задачка которую никак не могу решить уже целую неделю. Главное не могу определиться с алгоритмом. Прошу вас помочь если сможете конечно. И так задано 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.

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

Сообщение отредактировано: Bard - 10.01.2008 20:51

[Client]

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

Сообщение отредактировано: Client - 10.01.2008 21:05

[Michael_Rybak]

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

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

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

[Bard]

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

[volvo]

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

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

[Michael_Rybak]

Client, спасибо за помощь blum.gif но помоему я сделал тоже самое

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

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

[Bard]

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

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

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

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

Ограничения есть? На скорость выполнения, например?

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

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

Сообщение отредактировано: Bard - 10.01.2008 21:26

[Michael_Rybak]

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

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

[Bard]

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

[Michael_Rybak]

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

[Client]

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

[volvo]

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

 test_01.pas ( 949 байт ) Кол-во скачиваний: 347

[Bard]

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

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

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


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

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

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

[Michael_Rybak]

но тогда ведь у меня ошибка должна быть на время а у меня выдает неправильный ответ

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

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

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

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

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

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

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

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

как мне написать это условие и куда мне его поставить?

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

if cem+1<d[i+1] then begin writeln(cem+1); exit; end;

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

[Bard]

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

а вот и код программы:
 1515.pas ( 398 байт ) Кол-во скачиваний: 356

[Michael_Rybak]

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

[Client]

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

[Michael_Rybak]

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