Cod sursa(job #955079)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 30 mai 2013 20:38:23
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

struct st
{
	int s,x,y,z;
};

const int mo=10000;

st v[1000001];
int a[101],i,n,j,k,s,m,p,u,t,w,sum;
vector <int> e[10000];
bool ok;

bool cmp(st a,st b)
{
	return a.s<b.s;
}

int main()
{
	ifstream f("loto.in");
	ofstream g("loto.out");
	f >> n >> s;
	for (i=1;i<=n;i++)
		f >> a[i];
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
			{
				sum=a[i]+a[j]+a[k];
				ok=true;
				for (p=0;p<e[sum%mo].size();p++)
					if (e[sum%mo][p]==sum)
					{
						ok=false;
						break;
					}
				if (ok)
				{
					e[sum%mo].push_back(sum);
					t++;
					v[t].s=sum;
					v[t].x=a[i];
					v[t].y=a[j];
					v[t].z=a[k];
				}
			}
	sort(v+1,v+t+1,cmp);
	for (i=1;i<=t;i++)
	{
		p=1;u=t;w=s-v[i].s;
		while (p<=u)
		{
			m=(p+u)/2;
			if (v[m].s<w)
				p=m+1;
			else if (v[m].s>w)
				u=m-1;
			else 
			{
				g << v[i].x << ' ' << v[i].y << ' ' << v[i].z << ' ' << v[m].x << ' ' << v[m].y << ' ' << v[m].z;
				return 0;
			}
		}
	}
	g << -1;
	return 0;
}