Cod sursa(job #742994)

Utilizator vendettaSalajan Razvan vendetta Data 2 mai 2012 18:26:45
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <iostream>
#include <vector>

#define MOD 666013
#define nmax 105
using namespace std;

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

typedef struct{

    int a, b, c, nr;

}camp;

int a[nmax], n, s;
vector<camp> lista[MOD+10];

void citeste(){

    f >> n >> s;
    for(int i=1; i<=n; i++) f >> a[i];

}

vector<camp>::iterator afla_iter(int x){

    int rest = x % MOD;

    for(vector<camp>::iterator i=lista[rest].begin(); i!=lista[rest].end(); i++){
        if (x == (*i).nr) return i;
    }

    return (lista[rest].end());

}

void hash(){

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                int x = a[i] + a[j] + a[k];
                int rest = x % MOD;
                camp val;
                val.a = a[i];
                val.b = a[j];
                val.c = a[k];
                val.nr = x;
                if (afla_iter(x) == lista[rest].end())
                    lista[rest].push_back(val);
            }
        }
    }


}

void rezolva(){

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                int x = s - (a[i] + a[j] + a[k]);
                int rest = x % MOD;
                vector<camp>::iterator iter = afla_iter(x);
                if (iter != lista[rest].end()){
                    g << a[i] << " " << a[j] << " " << a[k] << " " << (*iter).a << " " << (*iter).b << " " << (*iter).c << "\n";
                    return;
                }
            }
        }
    }

}

int main(){

    citeste();
    hash();
    rezolva();

    return 0;

}