Cod sursa(job #1018181)

Utilizator stanescu.raduRadu Stanescu stanescu.radu Data 28 octombrie 2013 22:57:39
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>

using namespace std;
ifstream f ("loto.in");
ofstream g("loto.out");

struct suma
{
	int s;
	int x1,x2,x3;
};
int v[105],i,j,s,n,k,x;
suma a[10005];

void merge(int st,int x, int dr)
{
    int i=st, j=x+1, aux[105];
    int k=0;
    while (i<=x && j<=dr)
    {
        if (v[i]<v[j])
        {
            aux[++k]=v[i];
            i++;
        }
        else
        {
            aux[++k]=v[j];
            j++;
        }
    }
    while (i<=x)
    {
        aux[++k]=v[i];
        i++;
    }
    while (j<=dr)
    {
        aux[++k]=v[j];
        j++;
    }
    k=0;
    for (i=st;i<=dr;i++)
        v[i]=aux[++k];
}
 
void swap (int a, int b)
{
    if (v[a]>v[b])
    {
        int aux=v[a];
        v[a]=v[b];
        v[b]=aux;
    }
}
 
void merges(int s,int d)
{
    int x;
    if ((d-s)<1) swap(s,d);
    else
    {
        x=(s+d)/2;
        merges(s,x);
        merges(x+1,d);
        merge(s,x,d);
    }
}

int cautare (int x, int st, int dr)
{
	int i=st,j=dr;
	int m;
	if(i>j)
        return 0;
    else
        {
            m=(i+j)/2;
            if (x==a[m].s)
                return m;
            if (x<v[m])
                return cautare(x,i,m-1);
            else
                return cautare(x,m+1,j);
        }
}

int main ()
{
	f>>n>>s;
	for (i=1;i<=n;i++)
		f>>v[i];
	merges(1,n);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=n;k++)
			{
				a[i+j+k-2].s=v[i]+v[j]+v[k];
				a[i+j+k-2].x1=v[i];
				a[i+j+k-2].x2=v[j];
				a[i+j+k-2].x3=v[k];
			}
	i=1;
	k=0;
	while (!k)
	{
		x=s-a[i].s;
		j=cautare(x,1,n);
		if (j)
		{
			g<<a[i].x1<<" "<<a[i].x2<<" "<<a[i].x3<<" "<<a[j].x1<<" "<<a[j].x2<<" "<<a[j].x3;
			k=1;
		}
		i++;
	}
	if (k==0) g<<-1;
	f.close();
	g.close();
	return 0;
}