Cod sursa(job #1791608)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 29 octombrie 2016 15:40:33
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<fstream>
#include<algorithm>
#include<iostream>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");
const int NMAX = 1000005;

struct num{

    int a,b,c,sum;
};
num a[NMAX];
int N,S,v[105];

bool cmp(struct num a,struct num b)
{

    if(a.sum < b.sum)
        return true;
    return false;
}

int bin_search(int val,int left,int right)
{

    int mid;
    while(left <= right){
        mid = (left + right)>>1;
        if(a[mid].sum == val)
            return mid;
        if(a[mid].sum < val)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int main()
{

    in>>N>>S;
    for(int i = 1 ; i <= N ; ++i)
        in>>v[i];
    int lg = 0;
    for(int i = 1 ; i <= N ; ++i)
        for(int j = i ; j <= N ; ++j)
            for(int k = j ; k <= N ; ++k){

                a[++lg].a = v[i];
                a[lg].b = v[j];
                a[lg].c = v[k];
                a[lg].sum = v[i]+v[j]+v[k];
            }
    sort(a+1,a+lg+1,cmp);
    for(int i = 1 ; i <= lg ; ++i){
        int key = bin_search(S - a[i].sum,1,lg);
        if(key != -1){
            out<<a[i].a<<" "<<a[i].b<<" "<<a[i].c<<" "<<a[key].a<<" "<<a[key].b<<" "<<a[key].c;
            return 0;
        }
    }
    out<<-1;
    return 0;
}