Cod sursa(job #1480630)

Utilizator dnprxDan Pracsiu dnprx Data 2 septembrie 2015 22:08:35
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
#define modulo 123457

using namespace std;

struct Patru
{
    int s, x, y, z;
};

vector <Patru> h[modulo];
int a[103], n, S;

void Citire()
{
    int i;
    ifstream fin("loto.in");
    fin >> n >> S;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
    sort(a + 1, a + n + 1);
}

void ConstrHash()
{
    int i, j, k, rest;
    Patru w;
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            for (k = j; k <= n; k++)
            {
                w.s = a[i] + a[j] + a[k];
                w.x = i; w.y = j; w.z = k;
                rest = w.s % modulo;
                h[rest].push_back(w);
            }
}

Patru Cauta(int suma)
{
    int rest;
    unsigned i;
    Patru w;
    w.s = w.x = w.y = w.z = -1;
    rest = suma % modulo;
    for (i = 0; i < h[rest].size(); i++)
        if (suma == h[rest][i].s)
            return h[rest][i];
    return w;
}

void Rezolva()
{
    int i, j, k, suma;
    Patru w;
    ofstream fout("loto.out");
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            for (k = j; k <= n; k++)
            {
                suma = S - (a[i] + a[j] + a[k]);
                if (suma >= 0)
                {
                  w = Cauta(suma);
                  if (w.s != -1)
                  {
                    fout << a[i] << " " << a[j] << " " << a[k] << " ";
                    fout << w.x << " " << w.y << " " << w.z << "\n";
                    fout.close();
                    return ;
                  }
                }
            }
    fout << "-1\n";
    fout.close();
}

int main()
{
    Citire();
    ConstrHash();
    Rezolva();
    return 0;
}