Cod sursa(job #812313)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 13 noiembrie 2012 19:29:07
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <stdio.h>

using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

long v[100];
long n,s;
int nr=0;

struct grupa 
{
	long su;
	long a,b,c;
} ;
grupa sume[50000];
long t[50000];

void citeste()
{ int i;
	in>>n>>s;
	for (i=1;i<=n;i++)
		in>>v[i];
}

void compune()
{
	int i,j,k;
	for (i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{	
				++nr;
				t[nr]=v[i]+v[j]+v[k];
				sume[nr].su=v[i]+v[j]+v[k];
				sume[nr].a=v[i];
				sume[nr].b=v[j];
				sume[nr].c=v[k];
			}
				
}
int cauta(long t[17000],long sp,int n)
{
	int i,pas;
	for (pas=1;pas<n;pas<<=1);
	for (i=0;pas;pas>>=1)
	{
		if (i+pas<n && (t[i+pas]<=sp))
			i+=pas;}
	
	if (t[i]==sp) return i;
		else return -1;
}

void sorteaza(int n)
{
	for (int i=1;i<=nr-1;i++)
		for (int j=i+1;j<nr;j++)
		{
			if (t[i]>t[j])
			{
				long aux=t[i];
				t[i]=t[j];
				t[j]=aux;
				aux=sume[i].su;
				sume[i].su=sume[j].su;
				sume[j].su=aux;
				aux=sume[i].a;
				sume[i].a=sume[j].a;
				sume[j].a=aux;
				aux=sume[i].b;
				sume[i].b=sume[j].b;
				sume[j].b=aux;
				aux=sume[i].c;
				sume[i].c=sume[j].c;
				sume[j].c=aux;
			}
		}
}
				

int main()
{	int p,pi,pf;
	int ok=0;
	citeste();
	compune();
	sorteaza(nr);
	for (p=1;p<=nr;p++)
	{
		 long sup=s-sume[p].su;
		int j=cauta(t,sup,nr);
		if (j!=-1) 
		{
			pi=p;
			pf=j;
			ok=1;
			break;
		}
	}
	if (ok==0) out<<-1;
	else
	{
		out<<sume[pi].a<<' '<<sume[pi].b<<' '<<sume[pi].c<<' '<<sume[pf].a<<' '<<sume[pf].b<<' '<<sume[pf].c;
	}
	return 0;
}