Cod sursa(job #1728946)

Utilizator DiClauDan Claudiu DiClau Data 13 iulie 2016 22:04:50
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 105, L = 1000005, PUT = 1 << 19;
int v[N], sume[L], n, s, ct = 0, m, caut, sol[5], fin[10];
void bkt ()
{
    if (ct == 3)
    {
        sume[++m] = s;
        return;
    }
    int i;
    for (i = 1; i <= n; i++)
    {
        s += v[i];
        ct++;
        bkt ();
        s -= v[i];
        ct--;

    }
}
int cautBin (int x)
{
    int pas = PUT, sol = 0;
    while (pas != 0)
    {
        if (pas + sol <= m && sume[pas + sol] <= x)
            sol += pas;
        pas >>= 1;
    }
    return sol;
}
bool reconst ()
{
    if (ct == 3)
    {
        if (s == caut)
            return true;
        return false;
    }
    int i;
    for (i = 1; i <= n; i++)
    {
        sol[++ct] = v[i];
        s += v[i];
        if (reconst())
            return true;
        s -= v[i];
        ct--;
    }
    return false;
}
int main ()
{
    FILE *in, *out;
    in = fopen ("loto.in", "r");
    out = fopen ("loto.out", "w");
    int s2;
    fscanf (in, "%d%d", &n, &s2);
    int i;
    for (i = 1; i <= n; i++)
        fscanf (in, "%d", &v[i]);
    bkt ();
    i = 0;
    sort (sume + 1, sume + m + 1);
    int select = -1, gas;
    ct = 0;
    s = 0;
    for (i = 1; i <= m; i++)
    {
        while (sume[i] == select && i < m)
            i++;
        select = sume[i];
        gas = cautBin (s2 - select);
        if (select + sume[gas] == s2)
        {
            caut = select;
            reconst();
            fin[1] = sol[1]; fin[2] = sol[2]; fin[3] = sol[3];
            caut = sume[gas];
            ct = 0;
            s = 0;
            reconst();
            fin[4] = sol[1]; fin[5] = sol[2]; fin[6] = sol[3];
            int j;
            sort (fin + 1, fin + 7);
            for (j = 1; j <= 6; j++)
                fprintf (out, "%d ", fin[j]);
            return 0;
        }
    }
    fprintf (out, "-1");
    return 0;
}