Cod sursa(job #182673)

Utilizator gigi_becaliGigi Becali gigi_becali Data 21 aprilie 2008 10:24:27
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#include <string>

int a[101], x[1000001/6+2],n, S;
int N;
int b[1000001];
inline void afis(int S)
{
    int i,j,k;
    for(i=1;i<=n;++i)
	for(j=i;j<=n;++j)
	    for(k=j;k<=n;++k)
		if(a[i]+a[j]+a[k]==S)
		{
		    printf("%d %d %d ", a[i],a[j],a[k]);
		    return;
		}
}

inline int bsearch(int v)
{
    int i, cnt;
    for(i=1, cnt=(1<<20); cnt; cnt>>=1)
	if(i+cnt<=N)
	    if(x[i+cnt]<=v) i+=cnt;
    if(x[i]==v)return 1;
    return 0;
}

inline int rad(int n,int byte, int a[], int b[])
{
    int count[1024], index[1024];
    memset(count, 0, sizeof(count));
    int i;
    for(i=1;i<=N;++i) ++count[(a[i]>>byte)&1023];
    index[0]=1;
    for(i=1;i<1024;++i) index[i]=index[i-1]+count[i-1];
    for(i=1;i<=N;++i) b[count[(a[i]>>byte)&1023]++]=a[i];
}

inline void radix()
{
    rad(N, 0, x, b);
    rad(N, 10, b, x);
    rad(N, 20, x, b);
    for(int i=1;i<=N;++i) x[i]=b[i];
}


int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d %d\n", &n, &S);
    int i,j,k;
    for(i=1;i<=n;++i) scanf("%d ", &a[i]);

    for(i=1;i<=n;++i)
	for(j=i;j<=n;++j)
	    for(k=j;k<=n;++k)
		x[++N]=a[i]+a[j]+a[k];

    sort(x+1,x+N+1);
//radix();

    for(i=1;i<=N && x[i]<=S;++i)
	if(bsearch(S-x[i]))
	{
	    afis(S-x[i]);
	    afis(x[i]);
	    return 0;
	}


/*
     for(i=1;i<=n;++i)
	for(j=1;j<=n;++j)
	    for(k=1;k<=n;++k)
		if(binary_search(x+1,x+N+1, S-a[i]-a[j]-a[k]))
		{
		    printf("%d %d %d ", a[i], a[j], a[k]);
		    afis(S-a[i]-a[j]-a[k]);
		    return 0;
		}
		*/

    printf("-1\n");
    return 0;
}