Cod sursa(job #2975468)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 6 februarie 2023 16:49:33
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int DIM = 101;
const int HASH_VALUE = 1000007;

struct hashElem {
    int val, a, b, c;
};
vector<hashElem> hashTable[HASH_VALUE];
int n, s;
int nums[DIM];

inline auto getAddress(int hash, int value) {
    for (auto it = hashTable[hash].begin(); it != hashTable[hash].end(); it++)
        if (it->val == value)
            return it;
    return hashTable[hash].end();
}

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

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int k = j; k <= n; k++) {
                int sum = nums[i] + nums[j] + nums[k];
                int hash = sum % HASH_VALUE;
                auto hashAddress = getAddress(hash, sum);
                if (hashAddress == hashTable[hash].end())
                    hashTable[hash].push_back({ sum, nums[i], nums[j], nums[k]  });
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            for (int k = j; k <= n; k++) {
                int valueToSearch = s - (nums[i] + nums[j] + nums[k]);
                if (valueToSearch < 0) continue;
                int hash = valueToSearch % HASH_VALUE;
                auto hashAddress = getAddress(hash, valueToSearch);
                if (hashAddress != hashTable[hash].end()) {
                    fout << nums[i] << ' ' << nums[j] << ' ' << nums[k] << ' ';
                    fout << hashAddress->a << ' ' << hashAddress->b << ' ' << hashAddress->c;
                    return 0;
                }
            }
        }
    }

    fout << -1;

    return 0;
}