Cod sursa(job #1009941)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 14 octombrie 2013 00:15:29
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#define NMax 101
#define NSum 1000000+1
using namespace std;
struct SUM
{
	int suma;
	int x1, x2, x3;
};
int caut(int li, int ls, SUM *v, int suma)
{
	int m = (li + ls) / 2;
	if (v[m].suma == suma)
	{
		return m;
	}
	else
	{
		if (li < ls)
		{
			if (v[m].suma < suma)
				return caut(m+1, ls, v, suma);			
			else
				return caut(li, m-1, v, suma);
		}
		else
			return -1;
	}
}
int caut1(int li, int ls, SUM *v, int suma)
{
	if (li == ls || suma < v[0].suma)
		return 0;
	while ( li < ls )
	{
		int m = (li + ls) / 2;
		if ( v[m].suma < suma)
			li = m+1;
		else
			if (v[m].suma > suma)
				ls = m-1;
			else
				li = ls = m;
	}
	return li;
}
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
int main()
{
	FILE *f = fopen("loto.in", "r"), *g = fopen("loto.out", "w");
	int n; int s; int v[NMax];
	fscanf(f, "%d %d", &n, &s); 
	for (int i=0; i<n; i++)
	{
		fscanf(f, "%d", &v[i]);
	}
	SUM *sume = new SUM[NSum];
	int k = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int x = 0; x < n; x++)
			{
				int l = v[i] + v[j] + v[x];
				if ( l < s )
				{
					sume[k].suma = l;
					sume[k].x1 = v[i], sume[k].x2 = v[j], sume[k].x3 = v[x];
					k++;
				}
			}
	qsort(sume, k-1, sizeof(SUM), compare);
	int gasit = 0;
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			for (int x = 0; x<n; x++)
			{
				int l = v[i] + v[j] + v[x];
				int result = caut1(0, k-1, sume, s - l);
				if ( result >= 0)
				{
					fprintf(g, "%d %d %d %d %d %d", sume[result].x1, sume[result].x2, sume[result].x3, v[i], v[j], v[x]);
					fclose(f); fclose(g);
					delete sume; 
					return 0; 
				}
			}
	fprintf(g, "-1");
	delete sume; 
	fclose(f); fclose(g);
	return 0;
}