Cod sursa(job #1042681)

Utilizator vlad233Dragan Vlad vlad233 Data 27 noiembrie 2013 16:34:21
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>

using namespace std;

long long v[101];
struct nr
{
	int a,b,c,sum;
};

void merge(int st, int x, int dr)
{
    	int i,j,nr=0,a[500001];
	i=st;
	j=x+1;
	while (i<=x && j<=dr)
	{
		if (v[i]<v[j])
		{
			a[++nr]=v[i];
			i++;
		}
		else
		{
			a[++nr]=v[j];
			j++;
		}
	}
	while (i<=x)
	{
		a[++nr]=v[i];
		i++;
	}
	while (j<=dr)
	{
		a[++nr]=v[j];
		j++;
	}
	nr=0;
	for (i=st;i<=dr;i++)
		v[i]=a[++nr];
}

void mergesort(int s, int d)
{
	int x;
	if ((d-s)<1)
		return;
	else
	{
		x=(s+d)/2;
		mergesort(s,x);
		mergesort(x+1,d);
		merge(s,x,d);
	}
}

int cb(nr v[], int n, int x)
{
    int st=1,dr=n,m;
    while(st<=dr)
    {
		m=(st+dr)/2;
        if(x==v[m].sum) 
			return m;
		else
			if(x<v[m].sum) 
				dr=m-1;
			else 
				st=m+1;
    }
    return -1;
}

int main()
{
	int n,i,j,k,s,x,t=0,p=0,ok=0;
	nr e[500001];
	ifstream f("loto.in");
	f>>n>>s;
	for (i=1;i<=n;i++)
	{
		f>>x;
		if (x<=s)
			v[++t]=x;
	}
	f.close();
	mergesort(1,t);
	for (i=1;i<=t;i++)
		for (j=i;j<=t && v[i]+v[j]<=s;j++)
			for (k=j;k<=t && v[i]+v[j]+v[k]<=s;k++)
			{
				p++;
				e[p].a=v[i];
				e[p].b=v[j];
				e[p].c=v[k];
				e[p].sum=v[i]+v[j]+v[k];
			}
	ofstream g("loto.out");
	for (i=1;i<=p && ok==0;i++)
	{
		x=cb(e,p,s-e[i].sum);
		if (x!=-1)
		{
			g<<e[i].a<<" "<<e[i].b<<" "<<e[i].c<<" "<<e[x].a<<" "<<e[x].b<<" "<<e[x].c;
			ok=1;
		}
	}
	if (ok==0)
		g<<-1;
	g.close();
	return 0;
}