Cod sursa(job #2777510)

Utilizator Victor280605Victor Dragos Victor280605 Data 23 septembrie 2021 16:07:13
Problema Loto Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct Pair
{
    int sum;
    int x;
    int y;
    int z;
};
Pair P[105 * 105 * 105];
int sir[105];
int cnt;
int n;
int s;
void Read()
{
    in >> n >> s;
    for(int i = 1; i <= n; i++)
        in >> sir[i];
}
void createP()
{
    cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                cnt += 1;
                P[cnt].x = sir[i];
                P[cnt].y = sir[j];
                P[cnt].z = sir[k];
                P[cnt].sum = sir[i] + sir[j] + sir[k];
            }
        }
    }
}

int compare(Pair a, Pair b)
{
    return a.sum < b.sum;
}

void sortP()
{
    sort(P + 1, P + cnt + 1, compare);
}

Pair bin(int sum){
    int st = 1, dr = cnt, mij;
    while(st <= dr){
        mij = (st + dr) / 2;

        if(sum < P[mij].sum){
            dr = mij - 1;
        }

        else if(sum > P[mij].sum){
            st = mij + 1;
        }

        else{
            return P[mij];
        }
    }

    Pair notFound;
    notFound.sum = -1;
    return notFound;

}


int main()
{
    int i,j,k,suma;
    Read();
    createP();
    sortP();
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            for(k=1; k<=n; k++)
            {
                suma = s- sir[i] - sir[j] - sir[k];
                Pair elem = bin(suma);
                if (elem.sum != -1){
                    out << sir[i] << " " << sir[j] << " " << sir[k] << " " << elem.x << " " << elem.y << " " << elem.z << "\n";
                    return 0;
                }
            }
        }
    }
    out << -1;
}