Cod sursa(job #1279814)

Utilizator whoasdas dasdas who Data 30 noiembrie 2014 22:10:43
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <cstdlib>

#include <set>

using namespace std;

const int k = 6;
int n, s;
int v[101], sol[k];
set<int> h1, h2;

int cmp (const void *p1, const void *p2)
{
    int a = *(int*)p1, b = *(int*)p2;
    return a - b;
}

bool pb(int ii, int p, int ssol)
{
    if (ssol > s) {
        exit(1);
    }

    if (p == k - 1) {
        sol[p] = s - ssol;
        return (h1.find(s - ssol) != h1.end());
    }

    if (p == k - 2)
        if (h2.find(s - ssol) == h2.end())
            return false;

    for (int i = ii; i < n; i++) {
        if (ssol + v[i] * (k-p) > s)
            return false;

        sol[p] = v[i];
        if(pb(i, p + 1, ssol + v[i]))
            return true;
    }
    return false;
}


int main()
{
    FILE *in = fopen("loto.in", "r");
    FILE *out = fopen("loto.out", "w");
    fscanf(in, "%d %d", &n, &s);

    for (int i = 0; i < n; i++) {
        fscanf(in, "%d", &v[i]);
        h1.insert(v[i]);
    }
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            h2.insert(v[i] + v[j]);

    qsort(v, n, sizeof(int), cmp);

    if (pb(0, 0, 0)) {
        for (int i = 0; i < k; i++) {
            fprintf(out, "%d ", sol[i]);
        }
    } else {
        fprintf(out, "-1");
    }

    return 0;
}