Cod sursa(job #1008663)

Utilizator miu_mik93FMI - Paduraru Miruna miu_mik93 Data 11 octombrie 2013 15:57:16
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#define NMax 201
using namespace std;
int Divide(int li, int ls, int long long *v)
{
	int st = li, dr = ls; int long long x = v[li];
	while (st < dr)
	{
		while (st < dr && x <= v[dr])
			dr--;
		v[st] = v[dr];
		while (st < dr && x >= v[st])
			st++;
		v[dr] = v[st];
	}
	v[st] = x;
	return st;
}
void QuickSort(int li, int ls, int long long *v)
{
	int m = Divide(li, ls, v);
	if ( li < m-1 )
		QuickSort(li, m-1, v);
	if ( m+1 < ls )
		QuickSort(m+1, ls, v);
}
int caut(int li, int ls, int long long *v, int long long suma)
{
	if (li < ls)
	{
		int m = (li + ls) / 2;
		if (v[m] == suma)
		{
			return m;
		}
		else
		if (v[m] < suma)
			return caut(m+1, ls, v, suma);		
		else
		if (v[m] > suma)
			return caut(li, m-1, v, suma);
	}
	else
		return -1;
}
long long int rezultat[7];
int main()
{
	FILE *f = fopen("loto.in", "r"), *g = fopen("loto.out", "w");
	int n; int long long s, v[NMax];
	fscanf(f, "%d %lld", &n, &s); 
	for (int i=0; i<n; i++)
	{
		fscanf(f, "%lld", &v[i]);
	}
	QuickSort(0, n-1, v);
	int long long sume[NMax];
	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 long long l = v[i] + v[j] + v[x];
				if ( l < s )
					sume[k++] = l;
			}
	int gasit = 0, indice = 0;
	for (int i=0; i<n && !gasit; i++)
		for (int j=0; j<n && !gasit; j++)
			for (int x = 0; x<k && !gasit; x++)
			{
				int long long l = v[i] + v[j] + sume[x];
				int result = caut(0, n-1, v, s - l);
				if ( result >= 0)
				{
					gasit = 1;
					rezultat[0] = v[i], rezultat[1] = v[j], rezultat[2] = v[result];
					indice = x;
				}
			}
	if (gasit)
	{

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				for (int x = 0; x < n; x++)
					if (v[i] + v[j] + v[x] == sume[indice])
					{
						fprintf(g, "%lld %lld %lld %lld %lld %lld", rezultat[0], v[i], rezultat[1], v[j], rezultat[2], v[x]);
						return 0;
					}

	}
	fprintf(g, "-1");
	return 0;
}