Cod sursa(job #1040875)

Utilizator vlad233Dragan Vlad vlad233 Data 25 noiembrie 2013 01:31:18
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>

using namespace std;

unsigned long v[101];

void merge(int st, int x, int dr)
{
    int i,j,nr=0;
	unsigned long 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 main()
{
	int n,i,j,k,t=0,p=0,ok=0;
	long long s,x;
	struct nr
	{
		long a,b;
		long long sum;
	};
	nr e[20000];
	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);
	p=t;
	t=0;
	for (i=1;i<=p;i++)
		for (j=1;j<=p && v[i]+v[j]<=s;j++)
		{
			t++;
			e[t].a=v[i];
			e[t].b=v[j];
			e[t].sum=v[i]+v[j];
		}
	ofstream g("loto.out");
	for (i=1;i<=t && ok==0;i++)
		for (j=1;j<=t && e[i].sum+e[j].sum<=s && ok==0;j++)
			for (k=1;k<=t && e[i].sum+e[j].sum+e[k].sum<=s && ok==0;k++)
				if (e[i].sum+e[j].sum+e[k].sum==s)
				{
					g<<e[i].a<<" "<<e[i].b<<" "<<e[j].a<<" "<<e[j].b<<" "<<e[k].a<<" "<<e[k].b;
					ok=1;
				}
	if (ok==0)
		g<<-1;
	g.close();
	return 0;
}