Cod sursa(job #3143078)

Utilizator PetraPetra Hedesiu Petra Data 27 iulie 2023 16:12:26
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, s, mx;
struct p_entry {
    int sum, a, b, c;
};

inline bool operator< (p_entry &x, p_entry &y)
{
    return (x.sum < y.sum);
}

vector<int> v;
vector<p_entry> p;

int cautare_binara(int x, int st, int dr)
{
    if (st > dr) return 0;
    int mijl = (st + dr) / 2;
    if (p[mijl].sum == x) return mijl;
    if (p[mijl].sum > x) return cautare_binara(x, 0, mijl);
    if (p[mijl].sum < x) return cautare_binara(x, mijl + 1, dr);
}

int main()
{
    fin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        int x;
        fin >> x;
        mx = max(mx, x);
        v.push_back(x);
    }
    if (6 * mx < s)
    {
        fout << -1;
        return 0;
    }
    if (6 * mx == s)
    {
        for (int i = 0; i < 6; i++)
            fout << mx << " ";
        return 0;
    }

    for (int i = 0; i < v.size(); i++)
        for (int j = 0; j < v.size(); j++)
            for (int k = 0; k < v.size(); k++)
            {
                p.push_back({v[i]+v[j]+v[k], v[i], v[j], v[k]});
            }
    sort(p.begin(), p.end());
    for (int i = 0; i < p.size(); i++)
    {
        int poz = cautare_binara(s - p[i].sum, 0, p.size() - 1);
        if (poz)
        {
            v.clear();
            v.push_back(p[i].a);
            v.push_back(p[i].b);
            v.push_back(p[i].c);
            v.push_back(p[poz].a);
            v.push_back(p[poz].b);
            v.push_back(p[poz].c);
            sort(v.begin(), v.end());
            for (int j = 0; j < v.size(); j++)
                fout << v[j] << " ";
            return 0;
        }
    }
    fout << -1;
    return 0;
}