Cod sursa(job #474604)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 4 august 2010 13:24:05
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 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 ++)
                {
                    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 && 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;
            }
            if(Sum[middle].val < good)
                lf = middle + 1;
            if(Sum[middle].val > good)
                rm = middle;
        }
    }
        if(oki)
            fout << "-1";
   return 0;
}