Cod sursa(job #318348)

Utilizator hasegandaniHasegan Daniel hasegandani Data 28 mai 2009 08:42:41
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<stdio.h>
#include<algorithm>

#define nmax 128
#define smax 1000008

using namespace std;

int a[nmax],rez[7];
int n,s;

struct num3
{
    int sum,s1,s2,s3;
} b[smax];

bool cmp(num3 a,num3 b)
{
    return a.sum<b.sum;
}

void sort2(int st,int dr)
{
    int poz=st-1;
    
    for(int i=st;i<=dr;++i)
        if (rez[i]<=rez[dr])
            {
            int aux=rez[i];
            rez[i]=rez[++poz];
            rez[poz]=aux;
            }
            
    if (st<poz-1)   sort2(st,poz-1);
    if (poz+1<dr)   sort2(poz+1,dr);
}

int caut(int x,int st,int dr)
{
	int mij;
	while (st<=dr)
		{
			int mid=st+(dr-st)/2;
			if (b[mid].sum==x)
				return mid;
			if (x<b[mid].sum)
				dr=mid-1;
			else
            	st=mid+1;
		}
    return 0;
}

int main()
{
    int l=0,i;
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
	for(i=1;i<=n;++i)
        scanf("%d",&a[i]);
	for(i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
			for(int k=j;k<=n;++k)
				{
				b[++l].sum=a[i]+a[j]+a[k];
				b[l].s1=a[i];
				b[l].s2=a[j];
				b[l].s3=a[k];
				}
	int ns=l;
	sort(b+1,b+ns+1,cmp);
	int x=0,y=0;
	for(i=1;i<=ns && !y;++i)
		{
        if (s-b[i].sum>0)
            x=caut(s-b[i].sum,1,ns);
   //     printf("%d: %d + %d + %d, si caut: %d\n",b[i].sum,b[i].s1,b[i].s2,b[i].s3,s-b[i].sum);
		if (x)
			y=i;
		}

	if (!y)
		{
		printf("-1\n");
		return 0;
        }
    
    
    rez[1]=b[x].s1; 
    rez[2]=b[x].s2; 
    rez[3]=b[x].s3;
    rez[4]=b[y].s1; 
    rez[5]=b[y].s2; 
    rez[6]=b[y].s3;
   
    sort2(1,6);
    
    for(i=1;i<=6;++i)
        printf("%d ",rez[i]);
    printf("\n");
    
    
    return 0;
}