Cod sursa(job #2738122)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 5 aprilie 2021 14:41:04
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 101;
const int MOD = 666013;

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

int N, S;
int V[NMAX];

struct Hash
{
    int sum;
    int a, b, c;

};
vector < Hash > H[MOD];

void Read()
{
    fin >> N >> S;

    for( int i = 1; i <= N; ++i )
        fin >> V[i];

    sort(V+1, V+N+1 );

    for( int i = 1; i <= N; ++i )
        for( int j = i; j <= N; ++j )
            for( int k = j; k <= N; ++k )
                if( V[i] + V[j] + V[k] <= S)
            {
                int s = V[i] + V[j] + V[k];
                int mod = s%MOD;

                H[mod].push_back( {s, V[i], V[j], V[k]} );
            }
}

int BS( int x, int lf, int rg, int val )
{
    //cout << lf << ' ' << rg << ' ' << val << '\n';


    if( lf > rg ) return -1;

	int mid = rg - ( rg - lf ) / 2;


    if( H[x][mid].sum == val )return mid;
    if( H[x][mid].sum < val ) return BS( x, lf, mid - 1, val );
    else return BS( x, mid + 1, rg, val );

}

void Loto()

{

    for( int i = 1; i <= N; ++i )
        for( int j = i; j <= N; ++j )
            for( int k = j; k <= N; ++k )
                if( V[i] + V[j] + V[k] <= S)
            {
                int s = V[i] + V[j] + V[k];
                s = S - s;
                int mod = s%MOD;


                for( int pos = 0; pos < H[mod].size(); ++pos )
                    if( H[mod][pos].sum == s ){
                        fout << V[i] << ' ' << V[j] << ' ' << V[k] << ' ' << H[mod][pos].a << ' ' << H[mod][pos].b << ' ' << H[mod][pos].c;
                        return ;
                    }
            }


    fout << -1;
}

int main()
{
    Read();
    Loto();
    return 0;

}