Cod sursa(job #1394806)

Utilizator kagy85Kolumban Antal kagy85 Data 20 martie 2015 18:28:06
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
//az n meximalis erteke
const unsigned short MaxN=100, LottoNr=6;

typedef struct
{
    unsigned long sum, x[3];
} state;

typedef vector<state> num_vect;

num_vect v; //eltaroljuk azt is hogy hanyadik volt az elozo
unsigned long a[MaxN], s;
unsigned short n;

state gen_state(unsigned long x0, unsigned long x1, unsigned long x2)
{
    state tst;

    tst.sum=x0+x1+x2;
    tst.x[0]=x0;
    tst.x[1]=x1;
    tst.x[2]=x2;

    return tst;
}

bool comp_state(state st1, state st2)
{
    return st1.sum < st2.sum;
}

long bsearch_vect(unsigned long o)
{
    long i0=0, i1=v.size()-1, i2;

    while (i0+1<i1)
    {
        i2=(i0+i1)/2;
        if (v[i2].sum>o)
            i1=i2;
        else
            i0=i2; //es kesz is van
    }
    if (v[i0].sum==o)
        return i0;
    if (v[i1].sum==o)
        return i1;

    return -1;
}

int main(void)
{
    ifstream fi("loto.in", ios::in);
    ofstream fo("loto.out", ios::out);
    long i, j, k, l, nr=0;
    bool won=false;

    fi>>n>>s;
    for (i=0; i!=n; i++)
        fi>>a[i];
    v.reserve(n*n*n);
    for (i=0; i!=n; i++)
        for (j=0; j!=n; j++)
            for (k=0; k!=n; k++)
                if (a[i]+a[j]+a[k]<=s)
                    v.push_back(gen_state(a[i], a[j], a[k]));
    sort(v.begin(), v.end(), comp_state);
    for (i=0; (i<(long)v.size())&&(!won)&&(v[i].sum <= s-v[i].sum); i++)
    {
        if ((j=bsearch_vect(s-v[i].sum))!=-1)
        {
            won=true; //megvan a nyero kombinacio
            for (l=0; l!=3; l++)
            {
                fo<<(v[i].x[l]);
                fo<<' ';
                fo<<(v[j].x[l]);
                fo<<' ';
            }
        }
    }
    if (!won)
        fo<<-1;
    fo.close();
    fi.close();

    return 0;
}