Cod sursa(job #508279)

Utilizator mraresMardare Rares mrares Data 7 decembrie 2010 22:54:23
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#define nmax 101
#define mmax 500000

using namespace std;

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

long maxim, step;
long nr, n, S, rez, found, ind, suma;
long v[nmax];

struct lista
{
    long st, nd, rd, sum;
} a[mmax];

int cmp(lista x, lista y)
{
    return x.sum < y.sum;
}

int main()
{
    long i, j, k;
    int ok = 1;
    fin >> n >> S;
    for(i=1; i<=n; ++i)
        fin >> v[i];
    for(i=1; i<=n; ++i)
        for(j=i; j<=n; ++j)
            for(k=j; k<=n; ++k)
            {
                ++nr;
                a[nr].st = v[i];
                a[nr].nd = v[j];
                a[nr].rd = v[k];
                a[nr].sum = v[i] + v[j] + v[k];
            }
    sort(a+1, a+nr+1, cmp);
    //first try failed
    for(maxim = 1; maxim <=nr; maxim <<=1);
    for(i=1; i<=nr; ++i)
    {
        step = maxim;
        suma = S-a[i].sum;
        //caut binar
        for(j=0; step; step >>= 1)
            if(j+step <= nr && a[j+step].sum <= suma)
                j+=step;
        if(a[j].sum == suma)
        {
            // fout << S << "\n";
            fout << a[i].st << " " << a[i].nd << " " << a[i].rd << " " << a[j].st << " " << a[j].nd << " " << a[j].rd << "\n";
            ok = 0;
            break;
        }
    }
    if(ok) fout << "-1\n";
    return 0;
}