Cod sursa(job #110258)

Utilizator hazegirlCatalina Predoi hazegirl Data 25 noiembrie 2007 23:00:26
Problema Economie Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
//economie
#include<fstream.h>
long int n, m[1001],v[1001],gas,min,a;
void look(int s)
	{if(s==a) gas=1;
	for(int i=1;i<=min && s<a && gas==0;i++)
              look(s+v[i]);
	}

int sort(int p, int q)
{int st=p, dr=q, x=m[st];
while(st<dr)
	{while(st<dr && x<=m[dr])dr--;
	m[st]=m[dr];
	while(st<dr && x>=m[st])st++;
	m[dr]=m[st];
	}
m[st]=x;
return st;
}

void qsort(int p, int q)
{int m=sort(p,q);
if(m-1>p) qsort(p,m-1);
if(m+1<q) qsort(m+1,q);
}

int main()
{long int i;
ifstream f("economie.in");
ofstream g("economie.out");
f>>n;
for(i=1;i<=n;i++)
	f>>m[i];
qsort(1,n);
v[1]=m[1]; min=1;
if(m[2]%v[1]) v[++min]=m[2];
for(i=3;i<=n;i++)
	{a=m[i];
	 gas=0;
	 look(0);
	 if(gas==0)
		v[++min]=m[i];
	 }
g<<min<<'\n';
for(i=1;i<=min;i++)
	g<<v[i]<<'\n';
f.close();
g.close();
return 0;
}