Cod sursa(job #318344)

Utilizator ZillaMathe Bogdan Zilla Data 28 mai 2009 08:30:54
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <stdio.h>
#include <algorithm>

using namespace std;


#define Nmax 100

// PAVEL E PROST -> NU A FACUT COBAI
// POP CARMEN SUGE PULA
//  3 pentru unul
//  3 pentru toti
//       "Pop Carmen"


struct suma{
        int i,j,k,s;
};

suma b[Nmax*Nmax*Nmax+100];

int v[Nmax+10],n,s,cnt,contor,sum[10];

int cmp (suma a,suma b)
{
    return a.s<b.s;
}

void qsort(int st,int dr)
{
	int i=st,j=dr,mid=b[(st+dr)/2].s;
	suma tmp;
	do
		{
			while(b[i].s<mid)	++i;
			while(b[j].s>mid)	--j;
			if(i<=j)
				{
					tmp=b[i];
					b[i]=b[j];
					b[j]=tmp;
					++i;
					--j;
				}
		}while(i<=j);

	if(i<dr)	qsort(i,dr);
	if(j>st)	qsort(st,j);
}

int main()
{
	int i,j,k;

	freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
    
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    for(i=1;i<=n;++i)
        for(j=i;j<=n;++j)
            for(k=j;k<=n;++k)
                {
                    b[++cnt].s=v[i]+v[j]+v[k];
                    b[cnt].i=i;
                    b[cnt].j=j;
                    b[cnt].k=k;
                }
	qsort(1,cnt);
	int st=1,dr=cnt;
	while(st<=dr)
		{
			if(b[st].s+b[dr].s>s)
				--dr;
			else
				if(b[st].s+b[dr].s<s)
					++st;
				else
					{
						sum[++contor]=b[st].i;
						sum[++contor]=b[st].j;
						sum[++contor]=b[st].k;
						sum[++contor]=b[dr].i;
						sum[++contor]=b[dr].j;
						sum[++contor]=b[dr].k;
						dr=st+1;
					}
		}
	st=1;
	dr=cnt;
	if(contor==0)
	while(st<=dr)
		{
			if(b[st].s+b[dr].s>s)
				--dr;
			else
				if(b[st].s+b[dr].s<s)
					--dr;
				else
					{
						sum[++contor]=b[st].i;
						sum[++contor]=b[st].j;
						sum[++contor]=b[st].k;
						sum[++contor]=b[dr].i;
						sum[++contor]=b[dr].j;
						sum[++contor]=b[dr].k;
						dr=st+1;
					}
		}
  	sort(sum+1,sum+contor+1);
	if(contor==0)
		printf("-1");
	else
		printf("%d %d %d %d %d %d",sum[1],sum[2],sum[3],sum[4],sum[5],sum[6]);
	return 0;
}