Cod sursa(job #474615)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 4 august 2010 13:41:17
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#define nmax 105

using namespace std;

const char iname[] = "loto.in";
const char oname[] = "loto.out";

ifstream fin(iname);
ofstream fout(oname);

struct rez{int left, mid,  right,  val; };
rez Sum[nmax * nmax * nmax + 5];
int A[nmax];
int N, S, i, j, k, l;

struct cmp
{
    bool operator()(const rez &a, const rez &b)const
    {
        if(a.val < b.val)
            return 1;
        return 0;
    }
};


int main()
{
    fin >> N >> S;
    for(i = 1; i <= N; i ++)
        fin >> A[i];

    for(i = 1; i <= N; i ++)
        for(j = 1; j <= N; j ++)
            for(k = 1; k <= N; k ++)
                {
                    if(A[i] + A[j] + A[k] < S)

                    {
                        Sum[++l].val = A[i] + A[j] + A[k];
                        Sum[l].left = A[i];
                        Sum[l].mid = A[j];
                        Sum[l].right = A[k];
                    }
                }
    sort(Sum + 1, Sum + l + 1, cmp());
    int good, lf, rm, oki, middle;
    oki = 1;
    for(i = 1; i <= l; i ++)
    {
        good = S - Sum[i].val;
        lf = 1;
        rm = l;
        if(oki == 0)
            break;
        middle = (lf + rm) >> 1;
        while(lf <= rm)
        {
            if(lf == rm && Sum[lf].val != good)
                break;
            if(oki == 1)
            {
                middle = (lf + rm) >> 1;
                if(Sum[middle].val == good)
                {
                    oki = 0;
                    fout << Sum[i].left << " " << Sum[i].mid << " " << Sum[i].right << " " << Sum[middle].left << " " << Sum[middle].mid << " " << Sum[middle].right;
                    exit(0);
                }
                if(Sum[middle].val < good)
                    lf = middle + 1;
                if(Sum[middle].val > good)
                    rm = middle;
            }
        }
    }
        if(oki)
            fout << "-1";
   return 0;
}