Cod sursa(job #336821)

Utilizator Ionescu_MariaIonescu Maria-Dorina Ionescu_Maria Data 1 august 2009 17:34:05
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream.h>
#define nmax 101
int n,sw;
long v[nmax],s,s3[nmax*nmax*nmax],dim,r[7],s1,s2;
void cit()
{
	ifstream fin("loto.in");
	fin>>n>>s;
	for(int i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
}
void constr_sume_3()
{
	int i,j,k;
	dim=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				s3[++dim]=v[i]+v[j]+v[k];
}
long divide(long p,long q)
{
	long x=s3[p];
	long st=p,dr=q;
	while(st<dr)
	{
		while(st<dr&&s3[dr]>=x)
			dr--;
		s3[st]=s3[dr];
		while(st<dr&&s3[st]<=x)
			st++;
		s3[dr]=s3[st];
	}
	s3[st]=x;
	return st;
}
void Qsort(long p,long q)
{
	long m=divide(p,q);
	if(m-1>p)
		Qsort(p,m-1);
	if(m+1<q)
		Qsort(m+1,q);
}
long caut_binar(long p,long q)
{
	if(p>q)
		return -1;
	long m=(p+q)/2;
	if(s3[m]==s2)
		return m;
	if(s3[m]<s2)
		return caut_binar(m+1,q);
	return caut_binar(p,m-1);
}
void rez()
{
	sw=0;//Consideram ca nu exista doua sume s1 si s2 a i s1+s2=s
	long m;
	int i,j,k;
	for(i=1;i<=dim&&sw==0;i++)
	{
		s1=s3[i];
		s2=s-s1;
		m=caut_binar(1,dim);
		if(m!=-1)
			sw=1;
	}
	if(sw==1)
	{
		int g1=0,g2=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				for(k=1;k<=n;k++)
				{
					int sum=v[i]+v[j]+v[k];
					if(sum==s1)
					{
						r[1]=v[i]; r[2]=v[j]; r[3]=v[k];
						g1=1;
					}
					if(sum==s2)
					{
						r[4]=v[i]; r[5]=v[j]; r[6]=v[k];
						g2=1;
					}
				}
	}
	
}
void afis()
{
	ofstream fout("loto.out");
	if(sw==1)
		for(int i=1;i<=6;i++)
			fout<<r[i]<<" ";
		else
			fout<<-1;
	fout<<'\n';
	fout.close();
}
int main()
{
	cit();
	constr_sume_3();
	Qsort(1,dim);
	rez();
	afis();
	
	return 0;
}