Cod sursa(job #3130236)

Utilizator omaclearuMacelaru Octavian Andrei omaclearu Data 17 mai 2023 09:56:43
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct Suma {
    int x, y, z, s;

    Suma(int tx, int ty, int tz) : x(tx), y(ty), z(tz), s(tx + ty + tz) {}
};

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

class LotoSolver {
private:
    int n, s;
    vector<int> v;
    vector<Suma> sum;


    bool cmp(const Suma &x, const Suma &y) {
        return x.s < y.s;
    }

    int cautbin(int st, int dr, int rest) {
        int mid;
        while (st <= dr) {
            mid = (st + dr) / 2;
            if (sum[mid].s == rest)
                return mid;
            else if (sum[mid].s > rest)
                dr = mid - 1;
            else
                st = mid + 1;
        }
        return -1;
    }

    void adauga() {
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j)
                for (int k = j; k < n; ++k)
                    sum.push_back(Suma(v[i], v[j], v[k]));
    }

    pair<int, int>& makePair() {
        pair<int, int> rasp = make_pair(-1, -1);
        for (int i = 0; i < sum.size(); ++i) {
            rasp.first = cautbin(0, sum.size() - 1, s - sum[i].s);
            if (rasp.first != -1) {
                rasp.second = i;
                break;
            }
        }
        return rasp;
    }

    void verifica(pair<int, int> rasp) {
        if (rasp.first != -1) {
            out << sum[rasp.first].x << " " << sum[rasp.first].y << " " << sum[rasp.first].z << " "
                << sum[rasp.second].x << " " << sum[rasp.second].y << " " << sum[rasp.second].z;
        } else {
            out << -1;
        }
    }

public:
    void citire() {
        int x;
        in >> n >> s;
        for (int i = 0; i < n; ++i) {
            in >> x;
            v.push_back(x);
        }
    }

    void rezolvare() {
        adauga();

        sort(sum.begin(), sum.end(), [this](const Suma &x, const Suma &y) { return cmp(x, y); });

        auto rasp = makePair();

        verifica(rasp);

    }
};

int main() {
    LotoSolver solver;
    solver.citire();
    solver.rezolvare();
    return 0;
}