Moderator: Board moderators

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
Julien Cornebise wrote:Thank you

I'll try this as soon as I'll have recuperated from SWERC (it was today, and I'm a bit dead)...

Thank you
I would recommend reading this http://online-judge.uva.es/board/viewto ... 7371#47371
this is far more understandable then all IDA thing in vague terms.
it would be great if you replied this post. really.

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

### 529 - too slow

hello everyone . i have tried to solve this problem using dfs method. but it becomes extremely slow after input is >= 25. how do i make it faster. can u give me hints......

Code: Select all

``````# include <iostream>
# include <vector>

using namespace std;
int a[10000],p[10000],n,m=99999999;

void dfs(int sum,int s)
{
if(sum==n)
{
if(s<m){
m=s;
for(int j=0;j<s;j++)	p[j]=a[j];
}
return;
}

for(int i=s-1;i>=0;i--)
{
if((sum+a[i])<=n){
a[s]=sum+a[i];
dfs(sum+a[i],s+1);
}
}

}

int main()
{
int i;

while(cin>>n)
{

m=99999999;
a[0]=1;

dfs(1,1);

for(i=0;i<m;i++)
cout<<p[i]<<' ';

cout<<'\n';
}

return 0;
}
``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm