Cod sursa(job #1140725)

Utilizator classiusCobuz Andrei classius Data 12 martie 2014 10:47:43
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
//#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

ifstream cin("loto.in");
ofstream cout("loto.out");

int i,j,k,n,s,v[101],x;

struct conf{
    int sum;
    int a,b,c;
};

vector<conf> c;

bool cmp(conf x, conf y){
    return (x.sum<y.sum);
}

int main(){
    cin>>n>>s;

    for(i=1;i<=n;i++){
        cin>>v[i];
    }
    conf ax;
    ax.sum=-1000000000;

    c.push_back(ax);

    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            for(k=1;k<=n;k++){
                conf ax;
                ax.sum=v[i]+v[j]+v[k];
                ax.a=v[i];
                ax.b=v[j];
                ax.c=v[k];
                c.push_back(ax);
            }
        }
    }
    ax.sum=1000000000;
    c.push_back(ax);

    sort(c.begin(),c.end(),cmp);
    for(i=0;i<c.size();i++){
        int st=0;
        int dr=c.size()-1;
        while(st<dr){
            int mid=(st+dr)/2;
            if(c[i].sum+c[mid].sum<s){
                st=mid+1;
            }else{
                dr=mid;
            }
        }
        if(c[i].sum+c[st].sum==s){
            x=st;
            break;
        }
    }
    if(i<c.size()){
        cout<<c[i].a<<' '<<c[i].b<<' '<<c[i].c<<' '<<c[x].a<<' '<<c[x].b<<' '<<c[x].c;
    }else{
        cout<<-1;
    }
    return 0;
}