Cod sursa(job #182661)

Utilizator gigi_becaliGigi Becali gigi_becali Data 21 aprilie 2008 10:17:55
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
using namespace std;
#include <cstdio>
#include <algorithm>

int a[101], x[1000001],n, S;
int N;

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;
}

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);

/*
    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;
}