Cod sursa(job #611085)

Utilizator vlad2901Vlad Berindei vlad2901 Data 30 august 2011 17:11:49
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100

using namespace std;

struct suma
{
    int a, b, c, s;
} sum[NMAX*NMAX*NMAX];

int n, s, v[NMAX];

bool cmp(suma x, suma y)
{
    return x.s < y.s;
}

int main()
{

    int i, j, k, curent, left, right, middle, sol, pas;

    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);

    scanf("%d %d", &n, &s);

    for(i=0;i<n;++i)
    {
        scanf("%d", &v[i]);
    }

    //fac sume de cate 3 numere
    pas = 0;
    for(i=0;i<n;++i)
    {
        for(j=0;j<n;++j)
        {
            for(k=0;k<n;++k)
            {
                sum[pas].a = v[i];
                sum[pas].b = v[j];
                sum[pas].c = v[k];
                sum[pas].s = v[i] + v[j] + v[k];

                pas++;
            }
        }
    }

    sort(sum, sum + n*n*n, cmp);

    for(i=0;i<n*n*n;++i)
    {
        curent = s - sum[i].s; //suma pe care o caut

        if(curent > sum[i].s)
        {
            left = i;
            right = n*n*n-1;
        }
        else
        {
            left = 0;
            right = i;
        }

        sol = 0;

        while(left <= right)
        {
            middle = (left + right)/2;
            if(curent <= sum[middle].s)
            {
                sol = middle;
                right = middle-1;
            }
            else
            {
                left = middle+1;
            }
        }
        //verific daca am gasit solutie
        if(sum[sol].s == curent)
        {
            printf("%d %d %d %d %d %d\n", sum[i].a, sum[i].b, sum[i].c, sum[sol].a, sum[sol].b, sum[sol].c);
            return 0;
        }

    }
    printf("-1\n");
    return 0;
}