Cod sursa(job #808743)

Utilizator maritimCristian Lambru maritim Data 7 noiembrie 2012 11:03:39
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<stdio.h>
#include<vector>
using namespace std;

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

typedef struct suma
{
    int S,a,b,c;
};

typedef vector<suma>::iterator it;

#define MaxN 110
#define M 666013
#define MaxSol 10

int N,S;
int A[MaxN],SolV[MaxSol];
vector<suma> H[M];

void citire(void)
{
    fscanf(f,"%d %d",&N,&S);
    for(int i=1;i<=N;i++)
        fscanf(f,"%d ",&A[i]);
}

inline void add(int a,int b,int c)
{
    suma sum = {a+b+c,a,b,c};
    H[sum.S%M].push_back(sum);
}

inline suma find(int S)
{
    int x = S%M;

    for(it i=H[x].begin();i<H[x].end();i++)
        if(i->S == S)
            return *i;

    return {-1,-1,-1,-1};
}

void preprocesare(void)
{
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            for(int k=1;k<=N;k++)
                add(A[i],A[j],A[k]);                
}

void rezolvare(void)
{
    suma a;

    preprocesare();

    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            for(int k=1;k<=N;k++)
            {
                a = find(S-A[i]-A[j]-A[k]);
                if(a.S != -1)
                {
                    SolV[1] = A[i];SolV[2] = A[j];SolV[3] = A[k];
                    SolV[4] = a.a;SolV[5] = a.b;SolV[6] = a.c;
                    return ;
                }
            }
}

int main()
{
    citire();
    rezolvare();

    if(SolV[1])
    for(int i=1;i<=6;i++)
        fprintf(g,"%d ",SolV[i]);
    else
        fprintf(g,"-1\n");
}