Cod sursa(job #1654457)

Utilizator braisaMiron Raisa braisa Data 17 martie 2016 02:57:19
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <algorithm>
 
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
 
struct sum{
        int s,e1,e2,e3;
} M[1000100];
 
int N,S,A[110],m;
 
 
int cbin(int val)
{
    int i, step;
    for (step = 1; step < m; step <<= 1);
    for (i = 0; step; step >>= 1)
        if (i + step < m && M[i + step].s <= val)
           i += step;
    return i;
}
bool comp(sum a, sum b) {return a.s < b.s;}
int main(){
    fin >> N >> S;
    for(int i = 0;i<N;i++){
        fin >> A[i];
    }
     
    for(int i = 0;i<N;i++)
        for(int j = i;j<N;j++)
            for(int l = j;l<N;l++){
                    if(A[i] + A[j] + A[l] < 600000100){
                        M[m].s = A[i] + A[j] + A[l];
                        M[m].e1 = A[i];
                        M[m].e2 = A[j];
                        M[m++].e3 = A[l]; 
                    }
            }
    sort(M,M+m,comp);
    for(int i = 0;i<N;i++)
        for(int j = i;j<N;j++)
            for(int l = j;l<N;l++){
                int k = cbin(S-A[i]-A[j]-A[l]);
                if (A[i]+A[j]+A[l]+M[k].s == S){
                        fout << A[i] << ' '<<A[j] << ' ' << A[l] << ' ' << M[k].e1 << ' ' << M[k].e2 << ' ' << M[k].e3;
                        return 0;
                }
                 
            }
    fout << -1;
    return 0;
}