Cod sursa(job #976551)

Utilizator vlady1997Vlad Bucur vlady1997 Data 23 iulie 2013 14:03:06
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
        #include <cstdio>
        #include <vector>
        #include <algorithm>
        using namespace std;
        int a[112];
        struct loto
        {
            int x, y, z, suma;
        } ;
        loto v[1000005];
        bool cmp (loto x,loto y)
        {
            return x.suma<y.suma;
        }
        int main()
        {
            int n, s, i, j, k, it=0;
            freopen("loto.in","r",stdin);
            freopen("loto.out","w",stdout);
            scanf("%d%d",&n,&s);
            for (i=1; i<=n; i++) scanf("%d",&a[i]);
            for (i=1; i<=n; i++)
            {
                for (j=1; j<=n; j++)
                {
                    for (k=1; k<=n; k++)
                    {
                        if ((a[i]+a[j]+a[k])*2==s) {printf("%d %d %d %d %d %d",a[i],a[i],a[j],a[j],a[k],a[k]); return 0;}
                        else
                        {
                            it++;
                            v[it].x=a[i];
                            v[it].y=a[j];
                            v[it].z=a[k];
                            v[it].suma=a[i]+a[j]+a[k];
                        }
                    }
                }
            }
            sort(v+1,v+it+1,cmp);
            for (i=1; i<=it; i++)
            {
                int st=1; int dr=it; int s2=s-v[i].suma;
                while (st<=dr)
                {
                    int m=(st+dr)/2;
                    if (v[m].suma==s2)
                    {
                        printf("%d %d %d %d %d %d\n",v[i].x,v[i].y,v[i].z,v[m].x,v[m].y,v[m].z);
                        return 0;
                    }
                    else
                    {
                        if (v[m].suma<s2) st=m+1;
                        else dr=m-1;
                    }
                }
            }
            printf("-1");
            fclose(stdin);
            fclose(stdout);
            return 0;
        }