Cod sursa(job #3215367)

Utilizator Toni07Stoica Victor Toni07 Data 14 martie 2024 20:58:00
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;

int a[105], s, n;

struct Triplet {int x, y, z;};
unordered_map <int, Triplet> sum;

int main() {
    ifstream f ("loto.in");
    ofstream g ("loto.out");
    f >> n >> s;
    for(int i = 1; i <= n; i++) f >> a[i];
    // Populez unordered_map cu toate sumele de triplete => O(n^3)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                sum[a[i] + a[j] + a[k]] = {a[i], a[j], a[k]};
    // Caut solutia => O(n^3)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++) {
                int comp = s - (a[i] + a[j] + a[k]);
                if(sum.count(comp)) {
                    Triplet tr = sum[comp];
                    g << a[i] << " " << a[j] << " " << a[k] << " " << tr.x << " " << tr.y << " " << tr.z << "\n";
                    return 0;
                }
            }
    g << -1;
    return 0;
}