Cod sursa(job #3295591)

Utilizator eric.mesterEric Mestereaga eric.mester Data 6 mai 2025 21:04:57
Problema Loto Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
#define NMAX 102

using namespace std;///O(N^3 *logN) Meet in the middle

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

struct Sum{
    int s,v[3];
};

bool operator < (const Sum &a, const Sum &b)
{
    return a.s < b.s;///nu ma afecteaza ca se suprapun:-)
}

int N,M;
int A[NMAX];
set <Sum> sume;

int main()
{
    fin >> N >> M;
    for(int i=1;i<=N;i++){
        fin >> A[i];
    }
    for(int i1=1;i1<=N;i1++){
        for(int i2=i1;i2<=N;i2++){
            for(int i3=i2;i3<=N;i3++){
                int sum=A[i1]+A[i2]+A[i3];
                if(sum<M){
                    sume.insert({sum,{A[i1],A[i2],A[i3]}});
                }
            }
        }
    }
    for(int i1=1;i1<=N;i1++){
        for(int i2=i1;i2<=N;i2++){
            for(int i3=i2;i3<=N;i3++){
                auto diff =sume.find({M-(A[i1]+A[i2]+A[i3]),{0,0,0}});
                if(diff!=sume.end()){
                    fout << A[i1] << " " << A[i2] << " " << A[i3] << " ";
                    fout << (*diff).v[0] << " ";
                    fout << (*diff).v[1] << " ";
                    fout << (*diff).v[2] << " ";
                    return 0;
                }
            }
        }
    }
    fout << -1;
}