Массивы, хм!... Опции

[vovsik]

Не пойму. Вот задачка.
Дан неубывающий массив положительных чисел. найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза) .

[GLuk]

А что конкретно не поймешь?
Как ее на паскале написать? Или мож на асме?

[virt]

Код

{$A+,B-,D-,E+,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 16384,0,655360}
program minnemogu;
const Max_Chislo=1000;
var i,j,n:word;
   a:array[1..64000]of byte;
   x:word;
   l:longint;
   Max_Summa:word;

begin
  fillchar(a,sizeof(a),0);
  read(n);
  Max_Summa:=0;
  for i:=1 to n do
  begin
     read(x);
     Max_Summa:=Max_Summa+x;
     a[x]:=a[x]+1;
  end;
  for i:=0 to Max_Summa-1 do
  begin
     if a[i]>1 then
        begin
           l:=longint(i)+j;
           if l<=Max_Summa then a[l]:=a[l]+1;
        end;
     for j:=i+1 to Max_Summa do
        if (a[i]>0) and (a[j]>0) then
        begin
           l:=longint(i)+j;
           if l<=Max_Summa then a[l]:=a[l]+1;
        end;
{      writeln(i);}
  end;
  for i:=1 to Max_Summa+1 do
     if a[i]=0 then break;
  writeln(i);
  readln;
end.

Вот вроде должно работать.

[vovsik]

а Если я добавлю, что число действий - порядка размера массива? Что с этой шнягой делать?запарился совсем!

[zx1024]

Код

S=1;
for i := 1 to n do
begin
 if a[i] > S then
   break
 S := S + a[i]
end;
r := S

a - исходный НЕУБЫВАЮЩИЙ массив, n - его размер,
в r будет результат.

Сообщение отредактировано: zx1024 - 3.06.2004 15:43

[GLuk]

оффтоп

Что-то тебя zx1024 давно видно не было??