529 - Addition Chains

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter » Sat Jun 10, 2006 7:34 pm

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

Post by chetan » Fri Feb 23, 2007 3:50 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Feb 23, 2007 7:16 pm

You can use IDA* search.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 5 (500-599)”