Cod sursa(job #1563761)

Utilizator mariapascuMaria Pascu mariapascu Data 6 ianuarie 2016 17:00:53
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int MaxN = 104, MaxV = 1000004;
int n, S, a[MaxN], v[MaxV][4], p, sp[MaxV];

int main() {
    fin >> n >> S;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int k = j; k <= n; k++)
                v[++p][0] = a[i] + a[j] + a[k], v[p][1] = a[i],
                v[p][2] = a[j], v[p][3] = a[k], sp[p] = v[p][0];
    sort(sp + 1, sp + p + 1);
    bool f = false;
    for (int k = 1; k <= p && !f; k++) {
        int s = sp[k];
        int i = 1, j = p;
        while (i <= j) {
            int m = (i + j) / 2;
            if (s + sp[m] < S) i = m + 1;
            else j = m - 1;
        }
        if(s + sp[i] == S) {
            f = true;
            bool s1 = false, s2 = false;
            for (int q = 1; q <= p && (!s1 || !s2); q++) {
                if (s == v[q][0] && !s1) {
                    fout << v[q][1] << ' ' << v[q][2] << ' ' << v[q][3] << ' ';
                    s1 = true;
                }
                if (sp[i] == v[q][0] && !s2) {
                    fout << v[q][1] << ' ' << v[q][2] << ' ' << v[q][3] << ' ';
                    s2 = true;
                }
            }
        }
    }
    if (f == false) fout << -1;
    fin.close();
    fout.close();
    return 0;
}