Cod sursa(job #2380931)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 15 martie 2019 17:56:24
Problema Loto Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

#define FILE_NAME "loto"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

constexpr int MAX_NUMS = 100 + 4;
constexpr int MAX_TICKETS = MAX_NUMS * MAX_NUMS * MAX_NUMS;
struct ticket
{
    int sum;
    int x, y, z;
    ticket(int _x = 0, int _y = 0, int _z = 0)
    {
        x = _x, y = _y, z = _z;
        sum = x + y + z;
    }
};
ticket halfTicket[MAX_TICKETS];
int Nums[MAX_NUMS];
int N, S, K;

bool operator<(ticket &a, ticket &b)
{
    return a.sum < b.sum;
}

int main()
{
    in >> N >> S;
    for(int i = 0; i < N; ++i)
        in >> Nums[i];

    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            for(int k = 0; k < N; ++k)
                halfTicket[K++] = ticket(Nums[i], Nums[j], Nums[k]);

    sort(halfTicket, halfTicket + K);

    for(int i = 0; i < K; ++i)
    {
        ticket luckyTicket = halfTicket[i];
        int need = S - luckyTicket.sum;

        int st = i, dr = K-1;
        while(st <= dr)
        {
            int m = st + ((dr-st)>>1);
            if(halfTicket[m].sum == need)
            {
                out << luckyTicket.x << ' ' << luckyTicket.y << ' ' << luckyTicket.z << ' '
                    << halfTicket[m].x << ' ' << halfTicket[m].y << ' ' << halfTicket[m].z << '\n';
                return 0;
            }
            else if(halfTicket[m].sum < need)
                st = m + 1;
            else
                dr = m - 1;
        }
    }

    out << "-1\n";
    return 0;
}