Cod sursa(job #229201)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 9 decembrie 2008 17:58:13
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<cstdio>
#include<algorithm>
using namespace std;

int sum[1000000],a[100],k,i,n,s,j,l=0,mid,st,dr;;

struct poz{int sum,x,y,z;};
poz p[1000000];

bool operator<(const poz &a, const poz &b)
{       return (a.sum<b.sum);}

int main()
{       freopen("loto.in","r",stdin);
        freopen("loto.out","w",stdout);
        scanf("%d%d",&n,&s);
        for(i=0;i<n;++i)
                scanf("%d",&a[i]);--n;
        for(i=n;i>=0;--i)
                for(j=n;j>=0;--j)
                        for(k=n;k>=0;--k)
                                p[l].sum=a[i]+a[j]+a[k],
                                p[l].x=i,p[l].y=j,p[l++].z=k;
        l--;                        
        sort(p,p+l);
        for(i=0;i<l;++i)
        {       st=0,dr=l;
                while(st<=dr)
                {       mid=(st+dr)/2;
                        if(p[i].sum+p[mid].sum==s)
                        {       printf("%d %d %d %d %d %d",a[p[i].x],a[p[i].y],a[p[i].z],a[p[mid].x],a[p[mid].y],a[p[mid].z]);
                                return 0;
                        }
                        else    if(p[i].sum+p[mid].sum>s)
                                        dr=mid-1;
                                else
                                        st=mid+1;
                }
        }
        printf("-1");
        return 0;
}