Cod sursa(job #1190656)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 25 mai 2014 15:54:59
Problema Loto Scor 100
Compilator cpp Status done
Runda itmarathon Marime 2.29 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMax = 102, SMax = 600000000;

int N, S;
int a[NMax];
int nv;
int v[1000003];
const int INF = 2000000000;
int ans[10], nans;

int main()
{
    freopen("loto.in", "r", stdin);
    scanf("%d %d", &N, &S);
    for (int i = 1; i <= N; ++ i)
        scanf("%d", &a[i]);
    register int i, j, k;
    for (i = 1; i <= N; ++ i)
        for (j = 1; j <= N; ++ j)
            for (k = 1; k <= N; ++ k)
                v[++nv] = a[i] + a[j] + a[k];
    sort(v+1, v+nv+1);
    int ns, st, dr, mij;
    for (int ii = 1; ii <= nv; ++ ii)
    {
        ns = S - v[ii];
        st = 1, dr = nv;
        while (st <= dr)
        {
            mij = (st+dr) >> 1;
            if (v[mij] == ns)
            {
                freopen("loto.out", "w", stdout);
                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] == v[ii])
                            {
                                v[ii] = INF;
                                ans[++nans] = i;
                                ans[++nans] = j;
                                ans[++nans] = k;
                            }
                            if (a[i] + a[j] + a[k] == ns)
                            {
                                ns = INF;
                                ans[++nans] = i;
                                ans[++nans] = j;
                                ans[++nans] = k;
                            }
                            if (v[ii] == INF && ns == INF)
                            {
                                printf("%d", a[ans[1]]);
                                for (int i = 2; i <= 6; ++ i)
                                    printf(" %d", a[ans[i]]);
                                printf("\n");
                                return 0;
                            }
                        }
                return 0;
            }
            else if (v[mij] < ns)
                st = mij + 1;
            else
                dr = mij - 1;
        }
    }
    FILE *g = fopen("loto.out", "w");
    fprintf(g, "-1\n");
    fclose(g);
    return 0;
}