Cod sursa(job #81217)

Utilizator ScrazyRobert Szasz Scrazy Data 31 august 2007 19:33:50
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <stdio.h>
#include <algorithm>
#define NMax 103
using namespace std;

struct _nod{long a; long b; long c; long ss;};
typedef struct _nod nod;

long n, bb;
long p[NMax], db;
nod a[NMax*NMax*NMax];
long S, pS, ppS, x[7];

int cmp(nod a, nod b)
{
    return a.ss<b.ss;
}

long binary(long val)
{
    long long i, step;
    for (step = 1; step < db; step <<= 1);

    for (i=0; step; step >>= 1)
	if (i+step < db && a[i+step].ss <= val)
	    i+=step;
    return i;
}


int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    long i, j, k; 
    
    db=0;
    
    scanf("%ld %ld", &n, &S);
    for (i=1; i<=n; ++i)
	scanf("%ld", &p[i]);

    

    for (i=1; i<=n; ++i)
	for (j=1; j<=n; ++j)
	    for (k=1; k<=n; ++k)
	    {
		a[++db].ss=p[i]+p[j]+p[k];
		a[db].a=p[i];
		a[db].b=p[j];
		a[db].c=p[k];
	    }
   
    sort(a+1,a+db,cmp);
   


    for (i=1; i<=n; ++i)
	for (j=1; j<=n; ++j)
	    for (k=1; k<=n; ++k)
	    {
		pS=p[i]+p[j]+p[k];
		ppS=S-pS;
                
		bb=binary(ppS);

		pS+=a[bb].ss;

		if (S==pS)
		{

		    x[1]=p[i];
		    x[2]=p[j];
		    x[3]=p[k];
		    x[4]=a[bb].a;
		    x[5]=a[bb].b;
		    x[6]=a[bb].c;
		    sort(x+1,x+7);
		    for (int l=1; l<=5; ++l)
			printf("%ld ", x[l]);
		    printf("%ld\n", x[6]); 

		    fclose(stdin);
		    fclose(stdout);
		    return 0;
		}

	    }

    printf("-1\n");

    fclose(stdin);
    fclose(stdout);

    return 0;
}