Cod sursa(job #2687375)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 19 decembrie 2020 22:44:28
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <algorithm>
#include <fstream>
#include <vector>
#define MOD 974411
#define BAZA 4457
using namespace std;
int v[ 101 ], el[ 7 ], poz, n, s;
vector<int> sume[ MOD + 1 ];
int suma_de_cautat;

bool caut( int val, int element ){
    for( int i = 0; i < sume[ val ].size(); i++ )
        if( sume[ val ][ i ] == element )
            return true;
    return false;
}

int main()
{
    int i;
    ifstream cin( "loto.in" );
    cin >> n >> s;
    for( i = 0; i < n; i++ )
        cin >> v[ i ];
    cin.close();
    for( i = 0; i < n; i++ )
        for( int j = i; j < n; j++ )
            for( int k = j; k < n; k++ ){
                int suma = s - ( v[ i ] + v[ j ] + v[ k ] );
                if( suma > 0 ){
                    int val = ( ( long long )suma * BAZA ) % MOD;
                    int hash1 = ( ( long long )( v[ i ] + v[ j ] + v[ k ] ) * BAZA ) % MOD;
                    sume[ hash1 ].push_back( ( v[ i ] + v[ j ] + v[ k ] ) );
                    if( caut( val, suma ) ){
                        el[ poz++ ] = v[ i ];
                        el[ poz++ ] = v[ j ];
                        el[ poz++ ] = v[ k ];
                        suma_de_cautat = suma;
                        i = j = k = n + 10;
                    }
                }
            }
    if( i == n ){
        ofstream cout( "loto.out" );
        cout << "-1\n";
    } else {
        for( i = 0; i < n; i++ )
            for( int j = i; j < n; j++ )
                for( int k = j; k < n; k++ )
                    if( v[ i ] + v[ j ] + v[ k ] == suma_de_cautat ){
                        el[ poz++ ] = v[ i ];
                        el[ poz++ ] = v[ j ];
                        el[ poz++ ] = v[ k ];
                        i = j = k = n + 10;
                    }
        sort( el, el + poz );
        ofstream cout( "loto.out" );
        for( i = 0; i < poz; i++ )
            cout << el[ i ] << ' ';
        cout << '\n';
    }

    return 0;
}