Cod sursa(job #2742451)

Utilizator amalia.gemanGeman Aamalia amalia.geman Data 20 aprilie 2021 22:39:40
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>
#define N 1100000

using namespace std;

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

int n, S, v[101], suma[N];
int nr, poz, st, dr, m, scurenta;
bool ok;

int main()
{
    // citire
    fin >> n >> S;
    for(int i = 1; i <= n; i++)
        fin >> v[i];

    // creare sume
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            for(int k = j; k <= n; k++)
                suma[++nr] = v[i] + v[j] + v[k];

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

    ok = 0;
    for(int i = 1; i <= n && ok == 0; i++)
        for(int j = 1; j <= n && ok == 0; j++)
            for(int k = 1; k <= n && ok == 0; k++)
            {
                st = 1;
                dr = nr;
                scurenta = v[i] + v[j] + v[k];

                while (st <= dr)
                {
                    m = (st + dr) / 2;
                    if(suma[m] == S - scurenta)
                    {
                        poz = m;
                        ok = 1;
                        break;
                    }
                    if(suma[m] < S - scurenta)
                        st = m + 1;
                    else
                        dr = m - 1;

                }
                if(ok == 1)
                    fout << v[i] << " " << v[j] << " " << v[k] << " ";
            }

    if (ok == 0)
    {
        fout << -1;
    }
    else
    {
        for(int i = 1; i <= n; i++)
            for(int j = i; j <= n; j++)
                for(int k = j; k <= n; k++)
                    if(v[i] + v[j] + v[k] == suma[poz])
                    {
                        fout << v[i] << " " << v[j] << " " << v[k];
                        return 0;
                    }
    }

    return 0;
}