Разбиение числа на слагаемые

[p1r2o3]

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

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

Задачка откуда? И важен ли порядок чисел в разбиении? Если нет - детски простая динамика пишется легко и точно проходит (взгляните на задачу 1017 на Тимусе, я использовал там именно такую динамику, ограничения по времени 1 секунда, по памяти 16 мб, проходит, у меня
1017 C++ Accepted
0.078 2 813 КБ).
Если да - надо подумать над более красивым решением, можно просунуть и такое, но его надо будет дописать и доделать в ущерб красоте и простоте.

Да Из Тимуса.. Нет не идет же.. По времени... Или я что-то не то пишу... Как там вы написали?

[LeBron]

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

Да Из Тимуса.. Нет не идет же.. По времени... Или я что-то не то пишу... Как там вы написали?

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

[p1r2o3]

Так даже лучше)))
Вот мой код(((

var
n,i,k,l:longint;
function f(var n:longint; var k:longint):longint;
var  m,p:longint;
begin
 if (n<0) or (k<0) then
 f:=0
 else
 if (n=1) and (k>=1) then
  f:=1
 else
 if (k=1) and (n>1) then
  f:=0
 else
 if n=0 then
  f:=1
 else
 begin
 p:=k-1; m:=n-k;
 f:=f(n,p)+f(m,p);
 end;

end;

begin
readln(n);
  l:=f(n,n);
 writeln(l-1);
end.

[LeBron]

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

Так даже лучше)))
Вот мой код(((

Заведите массив и заполните его в цыкле (динамика от меньших значений к бОльшим), избавтесь от такой глупости в стиле горе-учителей, как рекурсия.
Она дает Вам примерно 150кратный проигрыш по времени.

[p1r2o3]

А с массивом тоже ведь не получается.

var n,i,k,l,j:longint;
    d:array[0..500, 0..500] of longint;
function f(var n:longint; var k:longint):longint;
  var  m,p:longint;
begin
 if d[n,k]=-3 then
  if (n<0) or (k<0) then d[n,k]:=0 else
  if (n=1) and (k>=1) then d[n,k]:=1  else
  if (k=1) and (n>1) then d[n,k]:=0 else
 if n=0 then d[n,k]:=1  else
 begin
  p:=k-1; m:=n-k;
  d[n,k]:=f(n,p)+f(m,p);
 end;
 f:=d[n,k];
end;

begin
for i:=0 to 500 do
for j:=0 to 500 do
d[i,j]:=-3;
readln(n);
  l:=f(n,n);
 writeln(l-1);
end.

проигрыш по памяти((

[NiCola999]

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

[p1r2o3]

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

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

В том что она похожа на задачку о размене монет вы правы(я полностью с этим солидарна) а вот то, что она решается в несколько строк вызывает сомнения.

var 
  a:array[2..10, 1..10] of integer;
  n,k,i,j:integer;
begin
  readln(n);
  k:=2;  
  a[2,1]:=1;
   while k<=n-1 do
     begin
       inc(k);
       a[k,k-1]:=1;
        i:=k-2;
        for j:=1 to k div 2 do
          a[k,k-j]:=1;
        i:=k-j-1;

       while i>=1 do
         begin
           a[k,i]:=a[k,i+1]+a[k-1,i+1];
           dec(i);
         end;
     end;

writeln(a[n,1]);
end.

Ладно, без рекурсии так без рекурсии, а тогда с этой программкой че не то не подскажете?

[LeBron]

Нда... Времени и желания что-то объяснять нету, так как после запрета рекурсии писать рекурсию еще раз... У меня сейчас отбор как раз, и время тратить на такое неохота. Если появится много лишнего времени - посмотрю на Ваш код и попробую поймать идею. А пока - в награждение за попытки ловите мой АС:

#include <iostream>
#include <math.h>
using namespace std;long long ar[700][700];long long i,q,j,a,ans;
int main(){
cin>>a;
for (i=1;i<=a-1;i++){ar[a-i][i]=1;}
for (i=a-1;i>=1;i--){for(j=1;j<=a-i;j++){for(q=j+1;q<=i;q++){ar[i-q][q]=ar[i-q][q]+ar[i][j];};};}
for(i=1;i<=a;i++){ans+=ar[0][i];}cout<<ans;
return 0;}

Все символ в символ без любых изменений, разбирайтесь. Не поймете - задавайте вопросы, буду завтра (надеюсь) и отвечу.

[p1r2o3]

а если скажу , что ничего не поняла.?

[LeBron]

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

а если скажу , что ничего не поняла.?

Мне то что, говорите, если хотите. Если совсем ничего - то не уверен, что смогу помочь. Можете для себя "отформатировать" и еще раз прочесть... Не помогло?.. Я не виноват

После считывания числа - 3 строки решения
Первая строка - заполняю базу динамики.
Вторая - заполняю динамический массив (фактически, эта строка - и есть все решение).
Третяя - подсчитываю ответ по готовой динтаблице.