Cod sursa(job #988074)

Utilizator manutrutaEmanuel Truta manutruta Data 21 august 2013 23:02:19
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
# include <iostream>
# include <fstream>
# include <vector>
# include <algorithm>
using namespace std;

# define MAXN 103
# define MOD 666013

//<parsare>
FILE * fin = fopen("loto.in", "r");
const unsigned maxb = 8192;
char buf[maxb];
unsigned ptr = maxb;

inline int getInt() {
    int nr = 0;
    while (buf[ptr] < '0' || '9' < buf[ptr]) {
        if (++ptr >= maxb) {
            fread(buf, maxb, 1, fin);
            ptr = 0;
        }
    }

    while ('0' <= buf[ptr] && buf[ptr] <= '9') {
        nr = nr * 10 + buf[ptr] - '0';
        if (++ptr >= maxb) {
            fread(buf, maxb, 1, fin);
            ptr = 0;
        }
    }
    return nr;
}

//</parsare>

ofstream g("loto.out");

struct punct{
    int sum;
    int a, b, c;
};

int n, s;
int a[MAXN];
vector<punct> hassh[MOD];

void addHash(punct x) {
    int aux = x.sum % MOD;
    hassh[aux].push_back(x);
}

bool existHash(int x) {
    if (x <= 0) {
        return false;
    }

    int aux = x % MOD;
    for (int i = 0; i < hassh[aux].size(); i++) {
        if (hassh[aux][i].sum == x) {
            return true;
        }
    }
    return false;
}

punct getHash(int x) {
    int aux = x % MOD;
    for (int i = 0; i < hassh[aux].size(); i++) {
        if (hassh[aux][i].sum == x) {
            return hassh[aux][i];
        }
    }
}

int main()
{
    n = getInt();
    s = getInt();
    for (int i = 1; i <= n; i++) {
        a[i] = getInt();
    }

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                punct aux;
                aux.sum = a[i] + a[j] + a[k];
                aux.a = a[i];
                aux.b = a[j];
                aux.c = a[k];
                addHash(aux);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                int aux = s - a[i] - a[j] - a[k];
                if (existHash(aux) == true) {
                    punct x = getHash(aux);
                    g << a[i] << ' ' << a[j] << ' ' << a[k] << ' ';
                    g << x.a << ' ' << x.b << ' ' << x.c;
                    return 0;
                }
            }
        }
    }
    g << -1;

    return 0;
}