Cod sursa(job #460667)

Utilizator deneoAdrian Craciun deneo Data 3 iunie 2010 16:20:10
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#define Max 101
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");

int n,s,l,v[Max],sum[600000];

void citire ()
{
  f>>n>>s;
  for (int i=1; i<=n; i++)
	f>>v[i];
  f.close ();
}

void partial_sums ()
{
  for (int i=1; i<=n; i++)
	for (int j=i; j<=n; j++)
	  for (int k=j
		; k<=n; k++)
		sum[++l]=v[i]+v[j]+v[k];
}

int bin_search (int x,int i,int j)
{
  int mid;
  while (i<=j)
  {
	mid=i+(j-i)/2;               
	if (x<=sum[mid]) j=mid-1;        
	  else i=mid+1;
  }
  return (x==sum[i]);
}

void abc( int aux)
{
   for (int p=1; p<=n; p++)
			for (int q=p; q<=n; q++)
			  for (int r=q; r<=n; r++)
if (aux==v[p]+v[q]+v[r])
  g<<v[p]<<" "<<v[q]<<" "<<v[r];
}
int write_numbers ()
{
  for (int i=1; i<=n; i++)
	for (int j=i; j<=n; j++)
	  for (int k=j; k<=n; k++) 
		if (bin_search (s-v[i]-v[j]-v[k],1,l))
		{
		  int aux=s-v[i]-v[j]-v[k];
		 
				
				  g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
				  abc(aux);
		  return 1;
		}
  return 0;
}

  
int main ()
{
  citire ();
  partial_sums ();
  sort (sum+1,sum+l);
  if (!write_numbers ())
	g<<-1;
  g.close ();
  return 0;
}