Cod sursa(job #1240686)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 11 octombrie 2014 22:00:24
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <algorithm>
#define DIM 110
using namespace std;

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

int B[DIM*DIM*DIM],A[DIM],x,n,S,k,v[DIM],i,j,y,C[7][DIM*DIM*DIM];
int caut_binara(){
    int st = 0,dr = x;
    int mid = (st + dr) / 2;
    while( st <= dr){
        if(B[mid] + B[i] > S){
            dr = mid - 1;
            mid = (st + dr) / 2;
        }
        else
            if(B[mid] + B[i] < S){
                st = mid + 1;
                mid = (st + dr) / 2;
        }
            else
                {
                    v[1] = C[1][i];
                    v[2] = C[2][i];
                    v[3] = C[3][i];
                    v[4] = C[1][mid];
                    v[5] = C[2][mid];
                    v[6] = C[3][mid];
                    sort(v + 1, v + n + 1);
                    return 1;
                }
    }

}
int main()
{
    fin >> n >> S;
    for(i  = 1; i <= n; i++)
        fin >> A[i];
    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[i] + A[j] + A[k];
                C[1][x] = A[i];
                C[2][x] = A[j];
                C[3][x] = A[k];
            }
    sort(B + 1,B + x + 1);

    for(i = 1; i <= n; i ++)
        if(caut_binara())
            break;
    for(i = 1; i <= 6; i++)
        fout << v[i] << " ";

    return 0;
}