Cod sursa(job #1572454)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 18 ianuarie 2016 22:13:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

const int dmax = 100;

struct LOTO {int s, x, y, z;};
LOTO m[dmax * dmax * dmax + 1];
int t;

int v[dmax + 1];

int N, S;

int Binary_Search(int x)
{
    int st, dr, mid;

    st = 1; dr = t;

    while(st <= dr)
    {
        mid = st + (dr - st)/2;

        if(m[ mid ].s == x) return mid;

        if(x > m[ mid ].s) st = mid + 1;
        else
            dr = mid - 1;
    }

    return -1;
}

bool exc(LOTO e1, LOTO e2)
{
    return e1.s < e2.s;
}

int main()
{
    int i, j, k;
    bool sol = false;

    in >> N >> S;

    for(i = 1; i <= N; i++) in >> v[i];

    for(i = 1; i <= N; i++)
        for(j = i; j <= N; j++)
            for(k = j; k <= N; k++)
            {
                m[++t].s = v[i] + v[j] + v[k];
                m[t].x = v[i];
                m[t].y = v[j];
                m[t].z = v[k];
            }

    sort(m + 1, m + t + 1, exc);

    for(i = 1; i <= N; i++)
        for(j = i; j <= N; j++)
            for(k = j; k <= N; k++)
            {
                int suma = S - (v[i] + v[j] + v[k]);

                int r = Binary_Search(suma);

                if(r != -1 && !sol)
                {
                    sol = true;

                    out << v[i] << " " << v[j] << " " << v[k] << " ";

                    out << m[ r ].x << " " << m[ r ].y << " " << m[ r ].z;
                }
            }

    if(!sol) out << -1;

    return 0;
}