Cod sursa(job #999270)

Utilizator cont_de_testeCont Teste cont_de_teste Data 19 septembrie 2013 19:25:21
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
	

    #include <iostream>
    #include <vector>
    #include <fstream>
    using namespace std;
     
    const int oo = 0x3f3f3f3f;
    const int MAX_N = 111;
    int n, s;
    int a[MAX_N];
     
     
    void read()
    {
        ifstream fin("loto.in");
        fin >> n >> s;
        for (int i = 1; i <= n; ++i)
        {
            fin >> a[i];
        }
        fin.close();
    }
     
     
    struct tr
    {
            int i, j, k;
            tr()
            {
                    i = j = k = 0;
            }
		inline int sum()
		{
			return a[i] + a[j] + a[k];
		}
    };
     
    inline tr make_tr(int i, int j, int k)
    {
            tr res;
            res.i = i; res.j = j; res.k = k;
            return res;
    }
     
    const int mod = 666013;
    vector<tr> hash[mod];
     
    inline void add(int i, int j, int k)
    {
            int elem = a[i] + a[j] + a[k];
            int line = elem % mod;
     
            for (vector<tr>::iterator it = hash[line].begin(); it != hash[line].end(); ++it)
            {
                    if (it->sum() == elem)
                    {
                            return ;
                    }
            }
    		
            hash[line].push_back(make_tr(i, j, k));
    }
     
    inline tr get(int elem)
    {
            int line = elem % mod;
            for (vector<tr>::iterator it = hash[line].begin(); it != hash[line].end(); ++it)
            {
                    if (it->sum() == elem)
                    {
                            return *it;
                    }
            }
     
            return make_tr(0, 0, 0);
    }
     
     
    void solve()
    {
            for (int i = 1; i <= n; ++i)
            {
                    for (int j = i; j <= n; ++j)
                    {
                            for (int k = j; k <= n; ++k)
                            {
                                    add(i, j, k);
                            }
                    }
            }
     
            ofstream fout("loto.out");
            for (int i = 1; i <= n; ++i)
            {
                    for (int j = i; j <= n; ++j)
                    {
                            for (int k = j; k <= n; ++k)
                            {
                                    tr sol = get(s - a[i] - a[j] - a[k]);

                                    if (sol.i)
                                    {
                                            fout << a[i] << ' ' << a[j] << ' ' << a[k] << ' ' << a[sol.i] << ' ' << a[sol.j] << ' ' << a[sol.k] << '\n';
                                            return ;
                                    }
                            }
                    }
            }
     
            fout << "-1\n";
    }
     
     
    int main()
    {
            read();
            solve();
    }