Cod sursa(job #1242216)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 14 octombrie 2014 08:09:44
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <algorithm>
#define DIM 110
using namespace std;

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

int A[DIM],x,n,S,k,v[DIM],i,j,y,st,dr,mid,S2;

struct loto{
   int a,b,c,d;

}B[DIM*DIM*DIM];
int cmp( const loto &z, const loto &m){
    if(z.a < m.a)
        return 1;
return 0;
}
/*int caut_binara(int S){
    int st = 1,dr = x;
    int mid = (st + dr) / 2;
    while( st <= dr){
        if(B[mid].a> S){
            dr = mid - 1;
            mid = (st + dr) / 2;
        }
        else
            if(B[mid].a < S){
                st = mid + 1;
                mid = (st + dr) / 2;
        }
            else
                {
                    v[1] = B[i].b;
                    v[2] = B[i].c;
                    v[3] = B[i].d;
                    v[4] = B[mid].b;
                    v[5] = B[mid].c;
                    v[6] = B[mid].d;
                    return 1;
                }
    }
    return 0;
} */
int main()
{
    fin >> n >> S;
    for(i  = 1; i <= n; i++)
        fin >> A[i];
    sort(A + 1, A + n + 1);
    if(A[n] * 6 < S){
        fout << -1;
        return 0;
    }
    for(i = 1;i <= n;i ++)
        for(j = 1;j <= n;j ++)
            for(k = 1;k <= n;k ++){
                B[++x].a = A[i] + A[j] + A[k];
                B[x].b = A[i];
                B[x].c = A[j];
                B[x].d = A[k];
            }
    sort(B + 1,B + x + 1,cmp);
    for(i = 1; i <= x; i ++){
		S2 = S - B[i].a;
         st = 1,dr = x;
    	 mid = (st + dr) / 2;
    	while( st <= dr){
        	if(B[mid].a> S2){
            	dr = mid - 1;
            	mid = (st + dr) / 2;
        	}
        	else
            	if(B[mid].a < S2){
                	st = mid + 1;
                	mid = (st + dr) / 2;
        	}
            	else
                	{
                    fout << B[i].b << " ";
					fout << B[i].c << " ";
					fout <<	B[i].d << " ";
                    fout << B[mid].b << " ";
                    fout << B[mid].c << " ";
                    fout << B[mid].d << " ";
                    return 0;
                	}
    	}
    }
    return 0;
}