Cod sursa(job #2896191)

Utilizator AntoniaPopoviciAntonia-Adelina Popovici AntoniaPopovici Data 29 aprilie 2022 21:04:33
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int sir[101];
int n, s, k;
int nr = 0;

bool operator<(loto x, loto y)
{
    return x.S < y.S;
}

struct loto
{
    int a, b, S;
};
loto sum[1000001];

int main()
{
    fin >> n >> s;
    for (int i = 1; i <= n; i++)
        fin >> sir[i];
    sort(sir + 1, sir + n + 1);
    nr = 1;
    int x;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int k = j; k <= n; k++)
            {
                x = sir[i] + sir[j] + sir[k];
                if (x <= s)
                {
                    sum[nr].S = x;
                    sum[nr].b = sir[j];
                    sum[nr++].a = sir[i];
                }
                else
                    break;
            }
    sort(sum, sum + nr);
    for (int i = 1; i <= nr; i++)
    {
        int x = s - sum[i].S;
        int s = 1, d = nr, mij, val;
        while (s != d)
        {
            mij = (s + d) >> 1;
            val = sum[mij].S;
            if (val == x)
            {
                fout << sum[i].a << " ";
                fout << sum[i].S - sum[i].a - sum[i].b << " ";
                fout << sum[i].b << " ";
                fout << sum[mij].b << " ";
                fout << sum[mij].a << " ";
                fout << sum[mij].S - sum[mij].a - sum[mij].b << " ";
                return;
            }
            if (val < x)
                s = mij + 1;
            else
                d = mij;
        }
    }
    fout << -1;
    return 0;
}