Cod sursa(job #79583)

Utilizator vladcoderVlad Ion vladcoder Data 23 august 2007 10:06:15
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <string.h>
#define FIN "loto.in"
#define FOUT "loto.out"
#define NMAX 112
typedef struct nod
{
	short int x, y, z;
} NOD;


int A[NMAX];
NOD B[NMAX*NMAX*NMAX];
int IND[NMAX*NMAX*NMAX];
int N, S, i, j, k, nr = 0;
FILE * fin, * fout;

int SUM( NOD T )
{
	return A[T.x] + A[T.y] + A[T.z];
}


void poz( int lo, int hi )
{
	int i = lo, j = hi, di = 0, dj = - 1, aux;
	while (i<j)
	{
		if ( SUM( B[IND[i]] ) > SUM( B[IND[j]] ) )
		{
			aux = IND[i]; IND[i] = IND[j]; IND[j] = aux;
			aux = di; di = - dj; dj = - aux;
		}
		i += di;
		j += dj;
	}
	k = i;
}
void quick( int lo, int hi )
{
	if ( lo < hi )
	{
		poz( lo, hi );
		quick( lo, k - 1 );
		quick( k + 1, hi );
	}
}

int BINARY( int lo, int hi, int value )
{
	int i = lo, step = 1;
	while ( step < hi ) step <<= 1;
	while (step)
	{
		if ( i + step <= hi )
			if ( SUM( B[IND[i+step]]) <= value ) i += step;
		step >>= 1;
	}
	if ( SUM( B[IND[i]] ) == value ) return IND[i]; else return 0;
}	


int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d %d\n", &N, &S );
	for( i = 1; i <= N; i++) fscanf( fin, "%d", &A[i] );
    for( i = 1; i <= N; i++)
		for( j = i; j <= N; j++)
			for( k = j; k <= N; k++)
			{
				nr++;
				B[nr].x = i; B[nr].y = j; B[nr].z = k;
				IND[nr] = nr;
			}

		quick( 1, nr );
		int found = 0;
		for( i = 1; i <= nr && !found; i++)
		{
		int	p = BINARY( 1, nr, S - SUM( B[IND[i]] ) );
			if (p)
			{
				found = 1;
				fprintf( fout, "%d %d %d %d %d %d\n", A[B[IND[i]].x], A[B[IND[i]].y], A[B[IND[i]].z],
                A[B[p].x], A[B[p].y], A[B[p].z] );
			}
		}
		if (!found) fprintf( fout, "%d\n", -1 );
		fclose( fin );
		fclose( fout );
	return 0;
}