Cod sursa(job #812423)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 13 noiembrie 2012 20:57:36
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>

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 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 quick_sort(long t[], int left,int right)
{
	int i=left;
	int j=right;
	int p=t[(left+right)/2];
	while (i<=j)
	{
		while ( t[i]>p ) 
			i++;
		while (t[j]<p) 
			j--;
		if (i<=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;
			i++;
			j--;
		}
	}
	if (left<j) quick_sort(t,left,j);
	if (i<right) quick_sort(t,i,right);
}

int main()
{	int p,pi,pf;
	int ok=0;
	citeste();
	compune();
	quick_sort(t,1,nr);
	for (p=1;p<=nr;p++)
	{
		 long sup=s-sume[p].su;
		int j=cauta(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;
}