Cod sursa(job #2093439)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 23 decembrie 2017 18:05:36
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>

using namespace std;

ifstream fin ("loto.in"); ofstream fout ("loto.out");

const int nmax = 100;

const int hbase = 666013;
const int hct = 2017;
const int mod = 1001023;

int v[nmax + 1];
bool ok;

struct str {
    int sum;
    int i, j, k;

    str () {
        sum = -1;
    }
};

str h[ mod ];

void baga (str x) {
    int pos = (1LL * x.sum * hbase + hct) % mod;
    while (h[ pos ].sum != -1 && h[ pos ].sum != x.sum) {
        pos = (1LL * pos * hbase + hct) % mod;
    }

    if (h[ pos ].sum == -1) {
        h[ pos ] = x;
    }
}

void cauta (int a, int b, int c, int r) {
    int pos = (1LL * r * hbase + hct) % mod;

    while (h[ pos ].sum != -1 && h[ pos ].sum != r) {
        pos = (1LL * pos * hbase + hct) % mod;
    }

    if (h[ pos ].sum == r) {
        fout << a << " " << b << " " << c << " " << h[ pos ].i << " " << h[ pos ].j << " " << h[ pos ].k << "\n";
        ok = 0;
        return ;
    }
}

int main () {
    int n, s;

    fin >> n >> s;
    for (int i = 1; i <= n; ++ i)
        fin >> v[ i ];

    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            for (int k = 1; k <= n; ++ k) {
                str shp;
                shp.sum = v[ i ] + v[ j ] + v[ k ];
                shp.i = v[ i ], shp.j = v[ j ], shp.k = v[ k ];

                baga( shp );
            }
        }
    }

    ok = 1;
    for (int i = 1; i <= n && ok; ++ i) {
        for (int j = 1; j <= n && ok; ++ j) {
            for (int k = 1; k <= n && ok; ++ k) {
                int sum = v[ i ] + v[ j ] + v[ k ];
                if (sum <= s) {
                    cauta(v[ i ], v[ j ], v[ k ], s - sum);
                }
            }
        }
    }

    if (ok) {
        fout << "-1\n";
    }

    fin.close();
    fout.close();
    return 0;
}