Выборка чисел

[LeBron]

Сообщение от Serge_Bliznykov

.

Поэтому, если для 25 элементов расчёт укладывается в две секунды (кстати, если не жалко - дайте плиз исходничек, будет очень любопытно поизучать/потестировать!), то для 26 - 4 сек, для 27 - 8 сек, для 28 - 16 сек. для 29 - 32 сек. для 30 - 1 мин 04 сек., для 31 - 2 м 8 сек, для 32 - 4 м 16 сек, для 33 - 8 м 32 сек, для 34 - 17 м 04 сек... вы ещё не утомились?

Говорил - напишу в будущем... Так вот, будущее уже настало Сегодня писал вот это:
Выражение
(Время: 1 сек. Память: 16 Мб Сложность: 56%)
Даны N целых чисел X1, X2, …, XN. Требуется расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому S.

Входные данные

Входной файл INPUT.TXT в первой строке содержит числа N и S. В следующей строке располагается N чисел, разделенных пробелом. Ограничения: 2 <= N <= 24, 0 <= Xi <= 5*107, -10^9 <= S <= 10^9.

Выходные данные

В выходной файл OUTPUT.TXT выведите «No solution», если такой результат получить невозможно, иначе выведите получившееся равенство. Если решение не единственное, выведите любое.
Сдесь перебор 2 в 23ем вариантов показал на тестировании 0.2 секунды. Вспомнил, что обещал написать код к задаче с этого форума, сел переделывать (ведь переделывать почти готовое решение всегда проще, чем писть с ноля), переделал, вот код:

var input,output:text;n,i,p,q,e,w:longint;
ara:array[-10..1000] of longint;
ss,ans,s:real;ar:array[-10..1000] of real;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
readln(input,n,s);
for i:=1 to n do begin read(input,ar[i]);ans:=ans+ar[i];end;
for i:=1 to n do ara[i]:=0;
q:=1;for i:=1 to n do q:=q*2;
p:=0;while (p<q)   do begin
if (abs(ss-s)<ans) and (ss<=s) then begin ans:=abs(ss-s);
  if (p<>0) then begin  e:=0;
    for i:=1 to n do begin if ara[i]=1 then begin if e=0 then begin e:=1;write(output,ar[i]:0:9); end
    else write(output,'+',ar[i]:0:9);end;end;writeln(output,'=',ss:0:9);  end; end;
inc(p);inc(ara[n]);ss:=ss+ar[n];
if ara[n]=2 then begin ss:=ss-2*ar[n];ara[n]:=0;w:=n-1;
while ara[w]=1 do begin ara[w]:=0;ss:=ss-ar[w];dec(w);end;ara[w]:=1;ss:=ss+ar[w];end;
end;

close(input);close(output);
end.

Итак, мои замечания по поводу моего же решения: 1. Минусы. Фатальных недочетов нету, и небыло даже перед дебагом с мелких проблем могу выделить "некрасивый вывод" - сделал позиционку, что бы не было матзаписи в фрипаскале, в зависимости от Вашего компилятора - можете убрать. Еще один минус - в зависимости от компилятора может коректно или некоректно работать сама вычислительная машина. То, что 1=0.(9) в некоторых компиляторах играет злую шутку (за несколько десятков или даже сотен миллионов итераций ошибка становиться довольно большой, у меня для 30 чисел в одном из компиляторов конечная ошибка составляла аж 0.00043). На большинстве фрипаскалей работает верно, так что я не виноват
2. Плюсы. Главный плюс - укладываеться в заявленые для 30 чисел 1 минуту. На моем рабочем компе в фрипаскале 2.сколькототам (влом сейчас лезть и смотреть точную версию) показывает для 30 случайных чисел время от 28.1 до 29.5 в зависимости от количества промежуточных лучших ответов и загружености компа в данный момент. Среднее время по 10 тестах - 28.47 секунды. Вижу места, где можно написать еще оптимальней (писал так, как привык, так как надо было просто, "что бы прошло", можно доделать "так, как лучше" вместо "так, как привычней").

[Serge_Bliznykov]

Главный плюс - укладываеться в заявленые для 30 чисел 1 минуту.

возможно.. но только это решение СОВСЕМ ДРУГОЙ задачи, а не той, которая обсуждалась в топике.. (главное отличие, что в выборке может быть от одного до N чисел, а у Вас, если я правильно понял, ВСЕ N чисел обязательно участвуют.. (да ещё и вычитаться могут... )

p.s. и ещё, мне кажется, что TC давно потерял интерес к данной теме...

[LeBron]

Сообщение от Serge_Bliznykov

возможно.. но только это решение СОВСЕМ ДРУГОЙ задачи, а не той, которая обсуждалась в топике.. (главное отличие, что в выборке может быть от одного до N чисел, а у Вас, если я правильно понял, ВСЕ N чисел обязательно участвуют.. (да ещё и вычитаться могут... )

p.s. и ещё, мне кажется, что TC давно потерял интерес к данной теме...

Хм... Возник вопрос - Вы программу запустить пробовали? Я обычно или запускаю, или прошу объяснить код словами, так как мне лень читать больше 20 строк кода. А Вы как сделали? Видимо, неправильно поняли. Я для большей наглядности даже на вывод промежуточные результаты бросил, видимо, точно не запускали.
З.Ы. Ну а по поводу ТС - мне как то с самого начала это было не особо важно. Я обычно берусь за задачу, если меня интересует задача. А не тогда, когда во мне вдруг просыпаеться мораль и желание помочь человеку (хм... когда такое в последний раз со мной было?)

[Serge_Bliznykov]

Сообщение от LeBron

Видимо, неправильно поняли.

Вы правы. Написал комментарий, только прочитав условия той задачи, которая Вам послужила "донором"... а программу не запустил.. ;(

Приношу свои извинения. код действительно рабочий.
всё работает!
единственное,

Сообщение от uber

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

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

p.s.
LeBron, а почему Вы так жутко пишете код?!
неужели так не лучше/понятнее/нагляднее/проще?!?!?

var
  input, output: text;
  n, i, p, q, e, w: longint;
  ara: array[-10..1000] of longint;
  ss, ans,
    s: real;
  ar: array[-10..1000] of real;
begin
  assign(input, 'in_nums.txt');
  reset(input);
  assign(output, 'out_nums.txt');
  rewrite(output);
  readln(input, n, s);
  for i := 1 to n do begin
    read(input, ar[i]);
    ans := ans + ar[i];
  end;

  { выведем массив чисел}
  for i := 1 to n do Write(ar[i]:5:2);
  WriteLn;


  for i := 1 to n do ara[i] := 0;
  q := 1;
  for i := 1 to n do q := q * 2;
  p := 0;
  while (p < q) do begin
    if (abs(ss - s) < ans) and (ss <= s) then
    begin ans := abs(ss - s);
      if (p <> 0) then
      begin
        e := 0;
        for i := 1 to n do
        begin
          if ara[i] = 1 then
          begin
            if e = 0 then
            begin
              e := 1;
              write(output, ar[i]: 0: 9);
            end
            else
              write(output, '+', ar[i]: 0: 9);
          end;
        end;
        writeln(output, '=', ss: 0: 9);
      end;
    end;
    inc(p);
    inc(ara[n]);
    ss := ss + ar[n];
    if ara[n] = 2 then
    begin
      ss := ss - 2 * ar[n];
      ara[n] := 0; w := n - 1;
      while ara[w] = 1 do
      begin
        ara[w] := 0;
        ss := ss - ar[w];
        dec(w);
      end;
      ara[w] := 1;
      ss := ss + ar[w];
    end;
  end;

  close(input); close(output);
end.

[LeBron]

Сообщение от Serge_Bliznykov

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

p.s.
LeBron, а почему Вы так жутко пишете код?!
неужели так не лучше/понятнее/нагляднее/проще?!?!?

Если речь идет о проверке на то, являеться ли максимальным количество слогаемых (при одинаковой сумме), то проверка увеличит время работы программы на треть (на треть от конечного, тоесть на половину от текущего). Если для определенного теста код работал минуту, то после улучшения будет работать примерно 90 секунд. Могу дописать, просто не видел этого дополнительного условия.
По поводу кода - сюда я его бросаю еще довольно красивым, разбивая на блоки "по назначению" и частично выделяя циклы и т.д. Мой рабочий код бывает хоть немного отформатированым только если задача достаточно сложная и я могу в ней запутаться. Если же я, начиная писать код, уже полностью знаю решение "в голове", то использую только обрезание по краю экрана, так мне удобней в том плане, что меньше надо скролить и код больше напоминает "обычный текст". В большинстве случаев у меня нету необходимости, что бы мой код кто-то читал (решаю олимпиадные задачи), поэтому я и не делаю его таким, что бы кому-то было удобно читать.
З.Ы. А реализция тупого перебора в этой задаче - еще не самое сложное, главное пряморуко написать.

[uber]

чего то я уже не понимаю Вас... и не только Вас..свою идею уже не понимаю.. и сомневаюсь в ней..


все же если перебирать из сортированных чисел - полчится выборка близкая к правде (с учетом epsilon) ..вобщем далеко от правды

[LeBron]

Сообщение от uber

чего то я уже не понимаю Вас... и не только Вас..свою идею уже не понимаю.. и сомневаюсь в ней..


все же если перебирать из сортированных чисел - полчится выборка близкая к правде (с учетом epsilon) ..вобщем далеко от правды

Можно математическую модель алгоритма? А то я Вас тоже не особо понимаю, и как-то не верю в полезность последующих попыток понять... А пока нечего анализировать, то и анализироать не получаеться.