Cod sursa(job #2626106)

Utilizator RomanacheRoman Alexandru-George Romanache Data 6 iunie 2020 11:55:09
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("loto.in");

ofstream out("loto.out");

const int N = 105;

int v[N],sums[N*N*N];

int main()

{

    int n,S;

    in >> n >> S;

    for (int i = 1; i<=n; i++)

        in >> v[i];

    int nr = 0;

    for (int i = 1; i<=n; i++)

        for (int j = i; j<=n; j++)

            for (int k = j; k<=n; k++)

                sums[++nr] = v[i]+v[j]+v[k];

    sort(sums+1,sums+nr+1);

    bool ok = 0;

    int poz = 0;

    for (int i = 1; i<=n && !ok; i++)

        for (int j = 1; j<=n && !ok; j++)

            for (int k = 1; k<=n && !ok; k++)

            {

                int st = 1, dr = nr, s = v[i]+v[j]+v[k];

                while (st<=dr)

                {

                    int mj = (st+dr)/2;

                    if (s+sums[mj] == S)

                    {

                        poz = mj;

                        ok = 1;

                        break;

                    }

                    if (s+sums[mj]>S)

                        dr = mj-1;

                    else

                        st = mj+1;

                }

                if (ok)

                    out << v[i] << " " << v[j] << " " << v[k] << " ";

            }

    if (!ok)

    {

        out << -1;

        return 0;

    }

    for (int i = 1; i<=n; i++)

        for (int j = 1; j<=n; j++)

            for (int k = 1; k<=n; k++)

                if (v[i]+v[j]+v[k] == sums[poz])

                {

                    out << v[i] << " " << v[j] << " " << v[k];

                    return 0;

                }

}