Cod sursa(job #866778)

Utilizator mariamFiciu Maria mariam Data 28 ianuarie 2013 19:08:22
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<algorithm>
#include<fstream>
using namespace std;
int b[100],v[101],i,n,m,k,l,p,s,j,dr,st,aux,ok;

struct elem {
	int s;
	int a;
	int b;
	int c;
};

elem a[1000010];

int cmp(elem x, elem y) {
	return x.s < y.s;
}

int main()
{
	ifstream f("loto.in");
	ofstream g("loto.out");
	f>>n>>s;p=s;
	for(i=1;i<=n;i++)
		f>>v[i];
	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++){
			for(k=j;k<=n;k++) {
				a[++l].s=v[i]+v[j]+v[k];
				a[l].a = v[i];
				a[l].b = v[j];
				a[l].c = v[k];
			}
		}
	}
	sort(a+1,a+l+1,cmp);
	for(i=1;i<=n && !(ok);i++)
		for(j=i;j<=n && !(ok);j++)
			for(k=j;k<=n && !ok;k++)
			{
				s=s-(v[i]+v[j]+v[k]);
				st=1;
				dr=n;
				while(st<=dr)
				{
					m=(st+dr)/2;
					if(a[m].s==s) 
					{
						b[1]=v[i];
						b[2]=v[j];
						b[3]=v[k];
						b[4]=a[m].a;
						b[5]=a[m].b;
						b[6]=a[m].c;
						ok = 1;
						break;
					}
					else 
						if(a[m].s<s)
							dr=m-1;
						else 
							st=dr+1;
				}
				s=p;
			}
	if(ok==0) {
		g<<"-1";
		return 0;
	}
	for(i=1;i<6;i++)
		for(j=i+1;j<=6;j++)
			if(b[i]>b[j])
			{
				aux=b[i];
				b[i]=b[j];
				b[j]=aux;
			}
	for(i=1;i<=6;i++)
		g<<b[i]<<" ";
	
	return 0;
}