Версия для печати темы

Автор: Bard 11.01.2008 0:48

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

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

Автор: Client 11.01.2008 1:05

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

Автор: Michael_Rybak 11.01.2008 1:09

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

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

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

Автор: Bard 11.01.2008 1:09

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

Автор: volvo 11.01.2008 1:11

Ограничения есть? На скорость выполнения, например? Если нет (и максимальное число в списке из N чисел не превосходит 255) - то можно чуть-чуть переработать вот это: http://forum.pascal.net.ru/index.php?s=&showtopic=6327&view=findpost&p=47388 и на приведенных тобой данных это выдаст правильный результат (проверил только что)...

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

Автор: Michael_Rybak 11.01.2008 1:13

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

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

Автор: Bard 11.01.2008 1:25

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


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



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

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

Автор: Michael_Rybak 11.01.2008 1:34

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

Автор: Bard 11.01.2008 1:59

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

Автор: Michael_Rybak 11.01.2008 2:24

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

Автор: Client 11.01.2008 2:30

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

Автор: volvo 11.01.2008 2:31

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

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

Автор: Bard 11.01.2008 2:44

эта здача с http://acm.timus.ru/problem.aspx?space=1&num=1515. я вот посылаю и проходит всего 3 теста ну вот поэтому я не знаю где у меня не проходит.

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


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


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

Автор: Michael_Rybak 11.01.2008 3:04

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





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

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

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

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

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


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



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

Автор: Bard 11.01.2008 3:23

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

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

Автор: Michael_Rybak 11.01.2008 3:37

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

Автор: Client 11.01.2008 10:42

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

Автор: Michael_Rybak 11.01.2008 16:21

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