Cod sursa(job #2405920)

Utilizator mariusn01Marius Nicoli mariusn01 Data 15 aprilie 2019 10:25:23
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>

using namespace std;
struct sumaTrei{
    int suma;
    int a;
    int b;
    int c;
};

sumaTrei t[1000001], aux;
int v[101];
int dim, st, dr, mid, i, j, k, n, s;
int cmp(const sumaTrei &x, const sumaTrei &y) {
    return x.suma < y.suma;
}

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

    fin>>n>>s;
    for (i=1;i<=n;i++)
        fin>>v[i];
    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++) {
                aux.a = v[i];
                aux.b = v[j];
                aux.c = v[k];
                aux.suma = v[i] + v[j] + v[k];
                dim++;
                t[dim] = aux;
            }

    sort(t+1, t+dim+1, cmp);

    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++) {
                int val = s-v[i]-v[j]-v[k];
                st = 1; dr = dim;
                while (st <= dr) {
                    int mid = (st + dr)/2;
                    if (t[mid].suma == val) {
                        fout<<t[mid].a<<" "<<t[mid].b<<" "<<t[mid].c<<" "<<v[i]<<" "<<v[j]<<" "<<v[k];
                        return 0;
                    }

                    if (val < t[mid].suma)
                        dr = mid-1;
                    else
                        st = mid+1;

                }
            }
    fout<<-1;
    return 0;
}