Cod sursa(job #370806)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 2 decembrie 2009 12:22:29
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct s3
{
    int suma,x,y,z;
};
const int N=1<<20;
s3 s[N+1];
int poqi,poqj,i,q,j,k,n,ss,v[7],a[102];
bool comp(const s3 &A,const s3 &B)
{
    if(A.suma<B.suma) return true;
    return false;
}
int cautb()
{
    int j,pas=N;
    for(j=0;pas;pas>>=1)
        if(j+pas<=q)
            if(s[j+pas].suma+s[i].suma<=ss)
                j+=pas;
    if(s[j].suma+s[i].suma!=ss) return 0;
    return j;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&ss);
    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++)
            {
                s[++q].suma=a[i]+a[j]+a[k];
                s[q].x=a[i];
                s[q].y=a[j];
                s[q].z=a[k];
            }
    sort(s+1,s+q+1,comp);
    for(i=1;i<=q;i++)
    {
        poqj=cautb();
        if(poqj!=0)
        {
            poqi=i;
            break;
        }
    }
    if(poqi==0 && poqj==0) printf("-1");
    else
    {
        v[1]=s[poqi].x;
        v[2]=s[poqi].y;
        v[3]=s[poqi].z;
        v[4]=s[poqj].x;
        v[5]=s[poqj].y;
        v[6]=s[poqj].z;
        sort(v+1,v+7);
        for(i=1;i<=6;i++)
            printf("%d ",v[i]);
    }
    return 0;
}