Cod sursa(job #1242124)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 13 octombrie 2014 23:31:35
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 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;

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

}B[DIM*DIM*DIM];
int cmp(loto z, 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 ++)
        if(caut_binara(S-B[i].a))
            break;
    for(i = 1; i <= 6; i++)
        fout << v[i] << " ";

    return 0;
}