Cod sursa(job #2924501)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 3 octombrie 2022 20:16:24
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <algorithm>

using namespace std;

#define Nmax 100
#define NrSol 6

int v[Nmax], sol[NrSol];

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

    int n, i, nr_ramase, l, r, mid, ssol, ok;
    long long s, sum;

    fin >> n >> s;

    for(i = 0; i < n; i++)
    {
        fin >> v[i];
    }

    sort(v, v + n);

    ok = 1;
    nr_ramase = NrSol;
    sum = 0;
    while(nr_ramase != 0)
    {
        if(sum + nr_ramase * v[n - 1] < s || sum + nr_ramase * v[0] > s)
        {
            ok = 0;
        }
        if(ok == 0)
        {
            break;
        }

        l = 0;
        r = n - 1;
        ssol = -1;
        while(l <= r)
        {
            mid = (l + r) / 2;
            if(sum + v[mid] * nr_ramase <= s)
            {
                ssol = v[mid];
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        sol[NrSol - nr_ramase] = ssol;
        sum += ssol;
        nr_ramase--;
    }

    sort(sol, sol + NrSol);

    if(sum != s)
    {
        ok = 0;
    }

    if(ok == 0)
    {
        fout << -1;
    }
    else
    {
        for(i = 0; i < NrSol; i++)
        {
            fout << sol[i] << " ";
        }
    }
    return 0;
}