Cod sursa(job #1742188)

Utilizator hanganflorinHangan Florin hanganflorin Data 15 august 2016 22:00:37
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>
#include <algorithm>
#define MAX 172000
using namespace std;

ifstream is("loto.in");
ofstream os("loto.out");

int n, S, s, a[101], x[7], nr, p1, p2;
struct Triplu{
    int a, b, c, suma;
}t[MAX];

const bool Cmp(const Triplu& t1, const Triplu& t2)
{
    return t1.suma < t2.suma;
}
int CautareBinara(int v); // returneaza pozitia unde avem suma v sau -1 daca nu avem

int main()
{
    is >> n >> S;
    for ( int i = 1; i <= n; ++i )
        is >> a[i];
    for ( int i = 1; i <= n; ++i )
        for ( int j = i; j <= n; ++j )
            for ( int k = j; k <= n; ++k )
            {
                t[nr].a = a[i];
                t[nr].b = a[j];
                t[nr].c = a[k];
                t[nr++].suma = a[i] + a[j] + a[k];
            }
    sort(t, t + nr, Cmp);
   // for ( int i = 0; i < nr; ++i )
    //    os << t[i].a << ' ' << t[i].b << ' ' << t[i].c << " = " << t[i].suma << '\n';
    for ( int i = 1; i < nr; ++i )
    {
        p1 = i;
        p2 = CautareBinara( S - t[i].suma );
        if ( p2 != -1 )
            break;
    }
    if ( p2 != -1 )
        os << t[p1].a << ' ' << t[p1].b << ' ' << t[p1].c << ' ' << t[p2].a << ' ' << t[p2].b << ' ' << t[p2].c;
    else
        os << -1;
    is.close();
    os.close();
    return 0;
}
int CautareBinara(int v)
{
    int st = 0, dr = nr-1, m;
    while ( st <= dr ) // oare si = ?
    {
        m = (st+dr)/2;
        if ( t[m].suma == v )
            return m;
        if ( t[m].suma > v )
            dr = m-1;
        if ( t[m].suma < v )
            st = m+1;
    }
    return -1;
}