Cod sursa(job #662379)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 16 ianuarie 2012 17:10:28
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <cstdio>
#include <algorithm>

#define MAX 105

using namespace std;

int v[MAX], sum[MAX*MAX*MAX];
int solutie[7];
int n, s, s2;

void citire()
{
    freopen("loto.in","r",stdin);
    scanf("%d %d\n", &n, &s);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &v[i]);
    }
    fclose(stdin);
}

void formareVectorSume()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                if(v[i] + v[j] + v[k] < s)
                {
                    sum[++sum[0]] = v[i] + v[j] + v[k];
                }
            }
        }
    }
    sort(sum + 1, sum + sum[0] + 1);
}

int search(int value)
{
    int left = 1, right = sum[0];
    int mij = (left + right) / 2;
    while(left <= right)
    {
        if(sum[mij] == value)
        {
            return mij;
        }
        if(value > sum[mij])
        {
            left = mij + 1;
        }
        else
        {
            right = mij - 1;
        }
        mij = (left + right) / 2;
    }
    return 0;
}

void findFirst()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = i; j <= n; j++)
        {
            for(int k = j; k <= n; k++)
            {
                if(search(s - v[i] - v[j] - v[k]))
                {
                    solutie[1] = i;
                    solutie[2] = j;
                    solutie[3] = k;
                    s2 = s - (v[i] + v[j] + v[k]);
                    break;
                }
            }
            if(solutie[1] == i)
                break;
        }
        if(solutie[1] == i)
            break;
    }
}

void findSecond()
{
    if(s != s2)
    {

        for(int i = 1; i <= n; i++)
        {
            for(int j = i; j <= n; j++)
            {
                for(int k = j; k <= n; k++)
                {
                    if(v[i] + v[j] + v[k] == s2)
                    {
                        solutie[4] = i;
                        solutie[5] = j;
                        solutie[6] = k;
                        break;
                    }
                }
                if(solutie[4] == i)
                    break;
            }
            if(solutie[4] == i)
                break;
        }
    }
}

void afisare()
{
    freopen("loto.out", "w", stdout);
    if(!solutie[1])
    {
        printf("-1");
    }
    else
    {
        sort(solutie + 1, solutie + 7);
        for(int i = 1; i <= 6; i++)
        {
            printf("%d ", solutie[i]);
        }
    }
    fclose(stdout);
}

int main()
{
    citire();
    formareVectorSume();
    findFirst();
    findSecond();
    afisare();
    return 0;
}