Cod sursa(job #615324)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 9 octombrie 2011 13:27:28
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct sume
{
    int sum;
    int x1;
    int x2;
    int x3;
};
sume s[400000];

int n,s1,v[100],nr[105],c,sol;

void cauta(int st, int dr, int x)
{
    int mij;
    sol=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x<s[mij].sum)
            dr=mij-1;
        else if(x>s[mij].sum)
            st=mij+1;
        else
        {
            sol=mij;
            return;
        }
    }
}

bool comp(sume a,sume b)
{
    return (a.sum<b.sum);
}

void back(int k)
{
    int i;
    if(k==3)
    {
        s[++c].sum=nr[v[1]]+nr[v[2]]+nr[v[3]];
        s[c].x1=v[1];
        s[c].x2=v[2];
        s[c].x3=v[3];
    }
    else
    for(i=1;i<=n;++i)
    {
        v[k+1]=i;
        back(k+1);
    }

}

int main()
{
    int i,j,k;
    freopen ("loto.in","r",stdin);
    freopen ("loto.out","w",stdout);
    scanf("%d %d",&n,&s1);
    for(i=1;i<=n;++i)
        scanf("%d",&nr[i]);
    back(0);
    sort(s+1,s+c+1,comp);
    for(i=1;i<=n;++i)
        for(j=i;j<=n;++j)
            for(k=j;k<=n;++k)
            {
                cauta(1,c,s1-nr[i]-nr[j]-nr[k]);
                if(sol!=-1)
                {
                    printf("%d %d %d %d %d %d",nr[i],nr[j],nr[k],s[sol].x1,s[sol].x2,s[sol].x3);
                    return 0;
                }
            }
    if(sol==-1)
        printf("-1");
    return 0;
}