Cod sursa(job #1997493)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 4 iulie 2017 15:01:05
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <algorithm>
#include <cstdio>

using namespace std;

struct suma
{
    int s, a, b, c;
}sum[1000002];

int x[101], sol[7];
int i, j, k, sx, n, aux, st, dr, m, nr;

bool cmp(suma x, suma y)
{
    return x.s<y.s;
}

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);

    scanf("%d%d", &n, &sx);
    for(i=1; i<=n; ++i) scanf("%d", &x[i]);
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j)
        {
            for(k=1; k<=n; ++k)
            {
                sum[++nr].s=x[i]+x[j]+x[k];
                sum[nr].a=x[i];
                sum[nr].b=x[j];
                sum[nr].c=x[k];
            }
        }
    }
    sort(sum+1, sum+nr+1, cmp);
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j)
        {
            for(k=1; k<=n; ++k)
            {
                st=1; dr=nr;
                aux=sx-x[i]-x[j]-x[k];
                while(st<=dr)
                {
                    m=(st+dr)/2;
                    if(sum[m].s<aux) st=m+1;
                    else if(sum[m].s>aux) dr=m-1;
                    else
                    {
                        sol[1]=sum[m].a;
                        sol[2]=sum[m].b;
                        sol[3]=sum[m].c;
                        sol[4]=x[i];
                        sol[5]=x[j];
                        sol[6]=x[k];
                        sort(sol+1, sol+7);
                        for(i=1; i<=6; ++i) printf("%d ", sol[i]);
                        return 0;
                    }
                }
            }
        }
    }
    printf("-1");
    return 0;
}