Cod sursa(job #1525772)

Utilizator BLz0rDospra Cristian BLz0r Data 15 noiembrie 2015 16:08:24
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 105
#define Mod 666013

FILE *f = fopen ( "loto.in", "r" );
FILE *g = fopen ( "loto.out", "w" );

struct GrupTrei{
    int x, y, z;
};

int v[Nmax];
vector < GrupTrei > Hash[Mod+5];

int GetVal ( int x, int y, int z ){
    return v[x] + v[y] + v[z];
}

int Key ( int val ){
    return val % Mod;
}

bool Hash_Search ( int &a, int &b, int &c, int val ){

    if ( val < 0 )
        return 0;

    int k = Key(val);

    vector < GrupTrei > :: iterator it;
    GrupTrei aux;

    for ( it = Hash[k].begin(); it != Hash[k].end(); ++it ){
        aux = *it;
        if ( GetVal(aux.x, aux.y, aux.z) == val ){
            a = aux.x;
            b = aux.y;
            c = aux.z;
            return 1;
        }
    }
    return 0;
}

void Hash_Insert ( int a, int b, int c, int val ){
    if ( !Hash_Search( a, b, c, val ) )
        Hash[Key(val)].push_back ( (GrupTrei) { a, b, c } );
}

int main(){

    int N, S;

    fscanf ( f, "%d%d", &N, &S );

    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%d", &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 ){
                int sum = GetVal(i,j,k);

                Hash_Insert ( i, j, k, sum );

                int a, b, c;
                if ( Hash_Search( a, b, c, S - sum ) ){
                    fprintf ( g, "%d %d %d %d %d %d", v[i], v[j], v[k], v[a], v[b], v[c] );
                    return 0;
                }
            }
        }
    }

    fprintf ( g, "-1" );

    return 0;
}