Cod sursa(job #1810166)

Utilizator kywyPApescu tiGEriu kywy Data 19 noiembrie 2016 17:59:32
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<algorithm>
#include<cstdio>
using namespace std;
int v[107], n, n3 ,sum, c[6];
struct suma
{
    int su;
    int nu1;
    int nu2;
    int nu3;
};
suma s[1000007];

bool comp(suma a, suma b)
{
    if(a.su < b.su) return 1;
    return 0;
}

int cautbin(int x)
{
    int start = 0, pas = 1;
    n3 = n * n * n;
    for(; pas <= n3; pas <<= 1);
    for(; pas; pas >>= 1)
    {
        int index = pas + start;
        if(index > n3) continue;
        else
        {
            if(s[index].su <= x) start = index;
        }
    }
    return start;
}
int main()
{
    FILE* in = fopen("loto.in", "r");
    FILE* out = fopen("loto.out", "w");
    fscanf(in, "%d%d", &n, &sum);
    n3 = 0;
    for(int i = 1; i <= n; ++i)
    {
        fscanf(in, "%d", &v[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int k = 1; k <= n; ++k)
            {
                ++n3;
                s[n3].su = v[i] + v[j] + v[k];
                s[n3].nu1 = v[i];
                s[n3].nu2 = v[j];
                s[n3].nu3 = v[k];
            }
        }
    }
    n3 = n * n * n;
    sort(s+1, s+n3+1, comp);
    for(int i = 1; i <= n3; ++i)
    {
        if(s[cautbin(sum - s[i].su)].su == sum - s[i].su)
        {
            c[1] = s[i].nu1;
            c[2] = s[i].nu2;
            c[3] = s[i].nu3;
            c[4] = s[cautbin(sum - s[i].su)].nu1;
            c[5] = s[cautbin(sum - s[i].su)].nu2;
            c[6] = s[cautbin(sum - s[i].su)].nu3;
            sort(c + 1, c + 7);
            fprintf(out, "%d %d %d %d %d %d",c[1], c[2], c[3], c[4], c[5], c[6]);
            return 0;
        }
    }
    fprintf(out, "-1");
}