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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ задача на динамику или же перебор

Автор: 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, спасибо за помощь blum.gif но помоему я сделал тоже самое wink.gif . Не всегда правильно где-то есть ошибка а наверняка и алгоритм получше есть yes2.gif .

Автор: 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, спасибо за помощь blum.gif но помоему я сделал тоже самое


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

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

Автор: Bard 11.01.2008 1:25

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


Да я это понял просто не сразу. Извиняюсь. Но в его алго ведь есть ошибка. вот например в этом примере 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, я же тебе сказал, твой алгоритм - правильный. И сказал, что нужно подправить. И спросил, на каком примере у тебя не работает. Ты меня игнорируешь? smile.gif

Автор: Client 11.01.2008 2:30

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

Автор: volvo 11.01.2008 2:31

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

Прикрепленный файл  test_01.pas ( 949 байт ) Кол-во скачиваний: 407

Автор: Bard 11.01.2008 2:44

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

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


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


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


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

Автор: Michael_Rybak 11.01.2008 3:04

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


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

Цитата
Добавь условие выхода из цикла на случай, если ответ равен сумме всех чисел + 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 11.01.2008 3:23

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

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

Автор: Michael_Rybak 11.01.2008 3:37

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

Автор: Client 11.01.2008 10:42

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

Автор: Michael_Rybak 11.01.2008 16:21

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