Cod sursa(job #1169576)

Utilizator 2dorTudor Ciurca 2dor Data 11 aprilie 2014 17:49:37
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;

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

const int MAXN = 105;

struct triplu {
    int a, b, c;
}element;

map<int, triplu> M;
int N, S, v[MAXN];

void Read() {
    fin >> N >> S;
    for (int i = 0; i < N; ++i)
        fin >> v[i];
    sort(v, v + N);
}

void Solve() {
    //first, we insert all the sums made up of 3 numbers into a map
    for (int i = 0; i < N; ++i) {
        element.a = v[i];
        for (int j = i; j < N; ++j) {
            element.b = v[j];
            for (int k = j; k < N; ++k) {
                element.c = v[k];
                if (M.find(v[i] + v[j] + v[k]) == M.end())//we didn't find this sum, so we assign a tuple to it
                    M.insert(make_pair(v[i] + v[j] + v[k], element));
            }
        }
    }
    //now, let's see if we can find two tuples that have the sum equal to S
    map<int, triplu>::iterator it;
    for (it = M.begin(); it != M.end(); ++it) {
        if (M.find(S - it->first) != M.end()) {//we have found a solution
            fout << it->second.a << ' ' << it->second.b << ' ' << it->second.c << ' ';
            it = M.find(S - it->first);
            fout << it->second.a << ' ' << it->second.b << ' ' << it->second.c << '\n';
            return;
        }
    }
    fout << -1 << '\n';
}

int main() {
    Read();
    Solve();
    fin.close();
    fout.close();
    return 0;
}