Cod sursa(job #283227)

Utilizator irene_mFMI Irina Iancu irene_m Data 18 martie 2009 21:13:07
Problema Economie Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream.h>
#define Vmax 50009
#define Nmax 1009
int v[Nmax],n,s[Vmax],k;

void cit()
{
	int i;
	ifstream fin("economie.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
}

void sol()
{
	int i,j,max=0,maxt;
	long l,aux;
	for(i=1;i<=n;i++)
	{
		maxt=max;
		for(j=maxt;j>=1;j--)
			if(s[j]!=0)
			{
				l=j+v[i]; aux=l;
				while(l<=Vmax)
				{
					if(l>max)
						max=l;
					s[l]=1;
					l+=aux;
				}
			}
		l=v[i]*2; aux=v[i];
		if(s[v[i]]==0)
			s[v[i]]=-1;
		while(l<=Vmax)
		{
			if(l>max)
				max=l;
			s[l]=1;
			l+=aux;
		}
	}
}

void numar()
{
	int nr=0,i,x;
	ofstream f("ec.out");
	for(i=1;i<=n;i++)
		if(s[v[i]]==-1)
		{
			f<<v[i]<<'\n';
			nr++;
		}
	f.close();
	ifstream g("ec.out");
	ofstream fout("economie.out");
	fout<<nr<<'\n';
	for(i=1;i<=nr;i++)
	{
		g>>x;
		fout<<x<<'\n';
	}
	g.close();
	fout.close();
}

void poz(int li,int ls)
{
	int i=li,j=ls,ii=0,jj=-1,c;
	while(i<j)
	{
		if(v[i]>=v[j])
		{
			c=v[i]; v[i]=v[j]; v[j]=c;
			c=ii;
			ii=-jj;
			jj=-c;
		}
		i+=ii;
		j+=jj;
	}
	k=i;
}

void quick(int li,int ls)
{
	if(li<ls)
	{
		poz(li,ls);
		quick(li,k-1);
		quick(k+1,ls);
	}
}

int main()
{
	cit();
	quick(1,n);
	sol();
	numar();
	return 0;
}