Cod sursa(job #338048)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 5 august 2009 12:38:51
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#define Max 101
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");

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

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];
}

void quicksort (int v[],int stanga, int dreapta)
{
  int i=stanga,j=dreapta;
  int pivot=v[(stanga+dreapta)>>1];
  while (v[i]<pivot) i++;
  while (v[j]>pivot) j--;
  if (i<j)
  {
	v[i]^=v[j]^=v[i]^=v[j];
	i++;
	j--;
  }
  else if (i==j) i++,j--;      //cand i=j rezulta ca &v[i]==&v[j] deci swap cu XOR nu merge
  if (stanga<j) quicksort (v,stanga,j);
  if (dreapta>i) quicksort (v,i,dreapta);
}

int bin_search (int x,int i,int j)
{
  int mid;
  while (i<=j)
  {
	mid=i+((j-i)>>1);               //((j-i)>>1) >> are prioritate mare si daca lasam fara paranteze considera ca
	if (x<sum[mid]) j=mid-1;        //expresie (i+(j-i))>>1
	else if (x>sum[mid]) i=mid+1;
	else return 1;
  }
  return 0;
}

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];
		  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[i]<<" "<<v[j]<<" "<<v[k]<<" "<<v[p]<<" "<<v[q]<<" "<<v[r];
		  return 1;
		}
  return 0;
}

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