Cod sursa(job #1282482)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 4 decembrie 2014 11:40:16
Problema Loto Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.45 kb
#include<cstdio>
#include<algorithm>

using namespace std;

int n, S, i, j, k, v[110], sum, w, sol;

struct sp
{
    int a, b, s;
};
sp sume[1000010];

int crit(sp x, sp y)
{
    return x.s < y.s;
}

int cautbin(int x)
{
    int l = 1, r = w, m;
    while(l <= r)
    {
        m = (l + r) / 2;
        if(sume[m].s == x) return m;
        if(sume[m].s > x) r = m - 1;
        if(sume[m].s < x) l = m + 1;
    }
    return -1;
}

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(k = j; k <= n; k++)
            {
                sum = v[i] + v[j] + v[k];
                w++;
                sume[w].a = v[i];
                sume[w].b = v[j];
                sume[w].s = sum;
            }

    sort(sume + 1, sume + w + 1, crit);

    for(i = 1; i <= w; i++)
    {
        sum = S - sume[i].s;
        sol = cautbin(sum);
        if(sol != -1)
        {
            printf("%d ", sume[i].a);
            printf("%d ", sume[i].b);
            printf("%d ", sume[i].s - sume[i].a - sume[i].b);
            printf("%d ", sume[sol].a);
            printf("%d ", sume[sol].b);
            printf("%d\n", sume[sol].s - sume[sol].a - sume[sol].b);
            return 0;
        }
    }

    printf("-1\n");

    return 0;
}