Cod sursa(job #698896)

Utilizator PatrikStepan Patrik Patrik Data 29 februarie 2012 16:34:54
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
	#include<stdio.h>
	#include<algorithm>
	using namespace std;
	FILE *f , *g ;
	int n ;
	long s , v[101] , s1[1000000] , sol[7] , sum  , si , l;
	bool sw;
	
	void citire();
	void solve();
	int caut(long x);
	
	int main()
	{
		citire();
		solve();
		return 0;
	}
	
	void citire()
	{
		f=fopen("loto.in" , "r" );
		fscanf(f , "%d%ld" , &n , &s );
		for( int i = 1 ; i<= n ; ++i )
			fscanf(f , "%ld" , &v[i] );
		fclose(f);
	}
	
	void solve()
	{
		g=fopen("loto.out" , "w" );
		for(int i = 1 ; i<= n ; ++i)
			for(int j = i ; j <= n ; ++j )
				for( int k = j ; k <= n ; ++k )
					if(v[i]+v[k] + v[j] <= s)
					s1[++l] = v[i]+ v[k] + v[j] ;
		sort(s1+1,s1+l+1);
		for(int i = 1 ; i<= n ; ++i )
			for(int j = i ; j<= n ; ++j )
				for( int k = j ; k <= n ; ++k )
				{
					si = v[i] + v[j] + v[k] ;
					if(caut(s-si))
					{
						sol[1] = v[i];
						sol[2] = v[j];
						sol[3] = v[k];
						sw = 1;
						j = n+1;
						i = n+1;
						s-=si;
						break;
					}
				}
		if(sw == 0)
			fprintf(g , "-1");
		else
		{
			for(int i  = 1 ; i<= n ; ++i )
				for( int j = i ; j<= n ; ++j )
					for( int k = j ; k <= n ;++k )
						if(v[i] + v[j] + v[k] == s )
						{
							sol[4] = v[i];
							sol[5] = v[j];
							sol[6] = v[k];
							j = n+1;
							i = n+1;
							break;
						}
			for(int i = 1 ; i<= 6 ; ++i )
				fprintf(g , "%ld " , sol[i]);
		}
		fclose(g);
	}
	
	int caut(long x)
	{
		int ls = 1 , ld = l , mid;
		while(ls <= ld )
		{
			mid = (ls+ld)/2;
			if(s1[mid] == x)
				return 1;
			else
				if(x > s1[mid])
					ls = mid+1;
				else
					ld = mid-1;
		}
		return 0;
	}