Cod sursa(job #926070)

Utilizator gbi250Gabriela Moldovan gbi250 Data 24 martie 2013 22:24:27
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <algorithm>

int n, v[101], nr, i, s, q, j;
long sol1[100000], sol[100000], sum_temp;

using namespace std;

int f(long x, long y)
{
    return (x<y);
}

int caut(long x)
{
    int ls=1, ld=nr, mij;
    while(ls<=ld)
    {
        mij=(ls+ld)/2;
        if(sol1[mij]==x)
            return mij;
        else if(sol1[mij]<x)
            ls=mij+1;
        else
            ld=mij-1;
    }
    return 0;
}
int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);

    scanf("%d %d", &n, &s);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);

    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(q=j;q<=n;q++)
                if(v[i]+v[j]+v[q]<=s)
                    sol1[++nr]=v[i]+v[j]+v[q];

    std::sort(sol1+1, sol1+nr+1, f);
    bool sw=0;

    for(i=1;i<=n&&!sw;i++)
        for(j=i;j<=n&&!sw;j++)
            for(q=j;q<=n&&!sw;q++)
            {
                sum_temp=v[i]+v[j]+v[q];
                if(caut(s-sum_temp))
                {
                    sol[1]=v[i]; sol[2]=v[j]; sol[3]=v[q];
                    sw=1; break;
                }
            }
    if(!sw)
        printf("-1\n");
    else
    {
        sw=0;
        for(i=1;i<=n&&!sw;i++)
            for(j=i;j<=n&&!sw;j++)
                for(q=j;q<=n&&!sw;q++)
                    if(s-sum_temp==v[i]+v[j]+v[q])
                    {
                        sol[4]=v[i]; sol[5]=v[j]; sol[6]=v[q];
                        sw=1; break;
                    }
        for(i=1;i<=6;i++)
            printf("%d ", sol[i]);
        printf("\n");
    }

    return 0;
}