Cod sursa(job #1816939)

Utilizator martonsSoos Marton martons Data 27 noiembrie 2016 10:15:22
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>

#define MOD 4656374
using namespace std;

struct comb{
    int a, b, c, sum;
    comb* next;
};

comb *h[MOD];

void add(comb *val){
    int pos = val->a + val->b + val->c;
    int mod = pos==0?0:pos%MOD;

    if(h[mod]==NULL){
        h[mod] = val;
        return;
    }

    comb* crt = h[mod];
    h[mod] = val;
    h[mod]->next=crt;
    /*while(crt->next!=NULL){
        crt = crt->next;
    }*/

    //crt->next = val;
}

comb* get(int sum){
    if(sum<0 || h[sum%MOD] == NULL)return NULL;
    int mod = sum==0?0:sum%MOD;
    comb* crt = h[mod];

    while(crt!=NULL){
        if(crt->sum == sum){
            return crt;
        }
        crt = crt->next;
    }
    return NULL;
}

int main()
{
    //ifstream in("loto.in");
    FILE* f = fopen("loto.in", "r");
    int n, s, v[100];

    //in>>n>>s;
    fscanf(f, "%d %d", &n, &s);
    for(int i=0;i<n;i++){
        //in>>v[i];
        fscanf(f, "%d", &v[i]);
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                add(new comb{v[i], v[j], v[k], v[i]+v[j]+v[k], NULL});
            }
        }
    }

    //ofstream out("loto.out");
    FILE *f1 = fopen("loto.out", "w");
    comb *c;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                if((c=get(s-v[i]-v[j]-v[k]))!=NULL){
                    //out<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "<<c->a<<" "<<c->b<<" "<<c->c;
                    fprintf(f1, "%d %d %d %d %d %d", v[i], v[j], v[k], c->a, c->b, c->c);
                    return 0;
                }
            }
        }
    }
    //out<<-1;
    fprintf(f1, "-1");
    return 0;
}