Cod sursa(job #508261)

Utilizator mraresMardare Rares mrares Data 7 decembrie 2010 22:32:33
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#define nmax 101

using namespace std;

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

int nr, n, S, rez, found, ind, sum;
int v[nmax];

struct lista
{
    int st, nd, rd, sum;
} a[nmax];

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

int main()
{
    int i, j, k, maxim, step;
    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+n+1, cmp);
    //first try failed
    for(maxim = 1; maxim <=nr; maxim <<=1);
    for(i=1; i<=nr; ++i)
    {
        step = maxim;
        sum = S-a[i].sum;
        //caut binar
        for(j=0; step; step >>= 1)
            if(j+step <= nr && a[j+step].sum <= sum)
                j+=step;
        if(a[j].sum == sum)
        {
            fout << S << "\n";
            fout << a[i].st << " " << a[i].nd << " " << a[i].rd << " " << a[j].st << " " << a[j].nd << " " << a[j].rd << "\n";
            return 0;
        }
    }
    fout << "-1\n";
    return 0;
}