Cod sursa(job #1145113)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 17 martie 2014 21:38:07
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

int N, S, x[101], CC;

struct C
{
    int fi;
    int se;
    int th;
    int sum;
    bool operator < (const C& s) const {
        return sum < s.sum;
    }
};

vector <C> V;

void Input();
void Generate();
void Solve();
int BinarySearch(int x);

int main()
{
    Input();
    Solve();

    is.close();
    os.close();
    return 0;
}

void Input()
{
    is >> N >> S;
    for ( int i = 1; i <= N; ++i )
        is >> x[i];
}

void Generate()
{
    C aux;
    for ( int i = 1; i <= N; ++i )
        for ( int j = i; j <= N; ++j )
            for ( int k = j; k <= N; ++k )
            {
                aux.fi = x[i];
                aux.se = x[j];
                aux.th = x[k];
                aux.sum = x[i]+x[j]+x[k];
                V.push_back(aux);
            }
}

void Solve()
{
    Generate();

    sort(V.begin(),V.end());

    for ( int i = 0; i < V.size(); ++i )
    {
        CC = BinarySearch(V[i].sum);
        if ( CC != -1 )
        {
            os << V[i].fi << " " << V[i].se << " " << V[i].th << " ";
            os << V[CC].fi << " " << V[CC].se << " " << V[CC].th;
            return;
        }
    }
    os << -1;
}

int BinarySearch(int x)
{
    int i, Step;
    for ( Step = 1; Step < V.size(); Step <<= 1);
    for (i = 0; Step; Step >>= 1)
    {
        if (i + Step < V.size() && V[i + Step].sum <= S-x )
           i += Step;
    }
    if ( V[i].sum == S-x )
    {
        CC = i;
        return i;
    }
    else
        return -1;
}