Cod sursa(job #3142931)

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

using namespace std;

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

int n, s, mx;
vector<int> v;
vector<pair<int, int>> p;

int cautare_binara(int x, int st, int dr)
{
    if (st > dr) return 0;
    int mijl = (st + dr) / 2;
    if (p[mijl].first == x) return mijl;
    if (p[mijl].first > x) return cautare_binara(x, 0, mijl);
    if (p[mijl].first < 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(make_pair(v[i]+v[j]+v[k], v[i]*100+v[j]*10+v[k]));
            }
    sort(p.begin(), p.end());
    for (int i = 0; i < p.size(); i++)
    {
        int poz = cautare_binara(s - p[i].first, 0, p.size() - 1);
        if (poz)
        {
            v.clear();
            int x1 = p[i].second, x2 = p[poz].second;
            while (x1 && x2)
            {
                v.push_back(x1 % 10);
                v.push_back(x2 % 10);
                x1 /= 10; x2 /= 10;
            }
            sort(v.begin(), v.end());
            for (int j = 0; j < v.size(); j++)
                fout << v[j] << " ";
            return 0;
        }
    }
    fout << -1;
    return 0;
}