Cod sursa(job #317040)

Utilizator hasegandaniHasegan Daniel hasegandani Data 22 mai 2009 11:18:59
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include<stdio.h>

#define nmax 128
#define smax 100

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

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

void sort(int st,int dr)
{
    int poz=st-1;
    
    for(int i=st;i<=dr;++i)
        if (b[i].sum<=b[dr].sum)
            {
            num3 aux=b[i];
            b[i]=b[++poz];
            b[poz]=aux;
            }
            
    if (st<poz-1)   sort(st,poz-1);
    if (poz+1<dr)   sort(poz+1,dr);
}

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)/2;
			if (b[mid].sum==x)
				return mid;
			if (b[mid].sum<x)
				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=1;j<=n;++j)
			for(int k=1;k<=n;++k)
				{
				b[++l].sum=a[i]+a[j]+a[k];
				b[l].s1=i;
				b[l].s2=j;
				b[l].s3=k;
				}
	int ns=n*n*n;
	sort(1,ns);
	int x,y=0;
	for(i=1;i<=ns && !y;++i)
		{
		x=caut(s-b[i].sum,1,n*n*n);
		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(int i=1;i<=6;++i)
        printf("%d ",rez[i]);
    printf("\n");
    
    
    return 0;
}