Cod sursa(job #2430015)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 12 iunie 2019 13:10:40
Problema Loto Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 107;

int t[DIM];

struct Suma
{
    int sum, f1, f2, f3;
};

vector <Suma> v;

bool cmp(Suma a, Suma b)
{
    return a.sum <= b.sum;
}

int main()
{
    int n, s;
    in >> n >> s;

    for(int i = 1; i <= n; i++)
    {
        in >> t[i];
    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
            {
                int sum = t[i] + t[j] + t[k];

                Suma el;

                el.sum = sum;
                el.f1 = t[i];
                el.f2 = t[j];
                el.f3 = t[k];

                v.push_back(el);
            }

    sort(v.begin(), v.end(), cmp);

    for(int i = 0; i < v.size() && v[i].sum * 2 <= s; i++)
    {
        int p = s - v[i].sum;

        int l = i;
        int r = v.size() - 1;

        while(l <= r)
        {
            int mid = (l + r) / 2;

            if(v[mid].sum  > p)
            {
                r = mid - 1;
            }
            else
                if(v[mid].sum < p)
                {
                    l = mid + 1;
                }
                else
                {
                    out << v[i].f1 << ' ' << v[i].f2 << ' ' << v[i].f3 << ' ' << v[mid].f1 << ' ' << v[mid].f2 << ' ' << v[mid].f3 << '\n';
                    return 0;
                }
        }
    }

    out << -1;
}