Cod sursa(job #1803249)

Utilizator Rares.IonescuRares Ionescu Rares.Ionescu Data 11 noiembrie 2016 10:05:37
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <algorithm>

const int MMAX = 1000005;
using namespace std;

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

struct loto {
    int a,b,c,s;
} L[MMAX];

struct cmp {
    bool operator()(const struct loto &A,const struct loto &B) {
        if(A.s < B.s)
            return 1;
        return 0;
    }
};


int V[105];

int Binsearch(int l,int r,const int &x) {
    int mid;
    while(l <= r) {
        mid = (l + r) >> 1;
        if(L[mid].s == x)
            return mid;
        if(L[mid].s < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;
}



int main(){
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,S,m = 0,poz;

    fin >> n >> S;

    for(int i = 1; i <= n; i++)
    {
        fin >> V[i];
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            for(int k = j; k <= n; k++)
            {
                L[++m].s = V[i] + V[j] + V[k];
                L[m].a = V[i];
                L[m].b = V[j];
                L[m].c = V[k];
            }
        }
    }

    sort(L + 1, L + m + 1, cmp());

    for(int i = 1; i <= m; i++)
    {
        poz = Binsearch(1,m,S - L[i].s);
        if(poz != -1)
        {
            fout << L[i].a << " " << L[i].b << " " << L[i].c << " " << L[poz].a << " " << L[poz].b << " " << L[poz].c;
            return 0;
        }
    }
    fout << -1;
    return 0;
}