Cod sursa(job #813315)

Utilizator cdascaluDascalu Cristian cdascalu Data 15 noiembrie 2012 10:31:37
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<stdio.h>
#include<vector>
#define Nmax 101
#define MOD 699967
using namespace std;
int N,S,v[Nmax];
vector<int> H[MOD];
void read_data()
{
	FILE*f = fopen("loto.in","r");
	fscanf(f,"%d%d",&N,&S);
	for(int i=1;i<=N;++i)
		fscanf(f,"%d",&v[i]);
	fclose(f);
}
void insert(int x)
{
    int poz = x%MOD;
    for(vector< int >::iterator it = H[poz].begin();it!= H[poz].end();++it)
    {
        if(*it == x)
        {
            return;
        }
    }
    H[poz].push_back( x );
}
int query(int x)
{
    if(x < 0)
        return 0;

    int poz = x%MOD;
    for(vector< int >::iterator it = H[poz].begin();it!=H[poz].end();++it)
    {
        if(*it == x)
        {
            return 1;
        }
    }
    return 0;
}
int main()
{
	read_data();
	int i,j,k,sum=-1;
	for(i=1;i<=N;++i)
		for(j=i;j<=N;++j)
			for(k=j;k<=N;++k)
				if(v[i] + v[j] + v[k] < S)
					insert(v[i] + v[j] + v[k]);
	
	FILE*g = fopen("loto.out","w");
	for(i=1;i<=N;++i)
		for(j=i;j<=N;++j)
			for(k=j;k<=N;++k)
				if(v[i] + v[j] + v[k] < S)
					if(query(S-v[i] - v[j] - v[k]))
					{
						fprintf(g,"%d %d %d ",v[i],v[j],v[k]);
						sum = S-v[i] - v[j] - v[k];
						i = j = k = N+1;
					}
	if(sum!=-1)
	{
		for(i=1;i<=N;++i)
			for(j=i;j<=N;++j)
				for(k=j;k<=N;++k)
					if(v[i] + v[j] + v[k] == sum)
					{
						fprintf(g,"%d %d %d\n",v[i],v[j],v[k]);
						i = j = k = N+1;						
					}
	}
	else
		fprintf(g,"-1\n");
	fclose(g);
	return 0;
}