Cod sursa(job #1265423)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 17 noiembrie 2014 12:11:46
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
#define Nmax 100

int v[Nmax], sum[Nmax * Nmax * Nmax];

int main()
{
    int i, j, k, n, s, nr = 0, x1, x2;
    int val, gasit = 0, st, dr, mijl;
    fin >> n >> s;
    
    for(i = 0; i < n; ++i) fin >> v[i];
    
    for(i = 0 ; i < n; ++i)
        for(j = 0 ; j < n; ++j)
            for(k = 0 ; k < n; ++k)
                if(v[i] + v[j] + v[k] < s)
                    sum[nr++] = v[i] + v[j] + v[k];
    
    sort(sum, sum + nr);
    
    for(i = 0; sum[i] <= (s >> 1) && !gasit; ++i)
    {
        val = s - sum[i];
        for(st = i, dr = nr - 1; st <= dr; )
        {
            mijl = (st + dr) >> 1;
            if(sum[mijl] == val) gasit = 1, x1 = sum[i], x2 = val;
            if(sum[mijl] < val) st = mijl + 1;
            else dr = mijl - 1;
        }
    }
    
    if(!gasit) {fout << "-1\n"; return 0;}
    
    bool gasit1 = 0, gasit2 = 0;
    for(i = 0 ; i < n; ++i)
        for(j = 0 ; j < n; ++j)
            for(k = 0 ; k < n; ++k)
            {
                if(!gasit1)
                    if(v[i] + v[j] + v[k] == x1)
                        fout << v[i] << ' ' << v[j] << ' ' << v[k] << ' ',
                        gasit1 = 1;
                if(!gasit2)
                    if(v[i] + v[j] + v[k] == x2)
                        fout << v[i] << ' ' << v[j] << ' ' << v[k] << ' ',
                        gasit2 = 1;
                if(gasit1 && gasit2) return 0;
            }
    return 0;
}