Cod sursa(job #568531)

Utilizator nautilusCohal Alexandru nautilus Data 31 martie 2011 13:08:40
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<map>
#define dmax 110
using namespace std;

typedef struct termen
{
 int s,e1,e2,e3;
} termen;

termen t[dmax*dmax*dmax];
map<int, bool> viz;
int n,s;
int a[dmax];
int sumc,poz,nr;


void citire()
{
 int i;
	
 ifstream fin("loto.in");
 
 fin>>n>>s;
 for (i=1; i<=n; i++)
	 fin>>a[i];
 
 fin.close();
}


bool comp(termen a, termen b)
{
 return a.s < b.s;
}


void cauta(int st, int dr)
{
 int mijl = (st + dr) / 2;
 
 if (st <= dr)
	 if (t[mijl].s == sumc)
		 poz = mijl; else
		 if (t[mijl].s > sumc)
			 cauta(st, mijl-1); else
			 cauta(mijl+1, dr);
}


void solve()
{
 int i,j,k;
 int gasit = 0,sum;
 
 ofstream fout("loto.out");
	
 for (i=1; i<=n; i++)
	 for (j=1; j<=n; j++)
		 for (k=1; k<=n; k++)
			 {
			  sum = a[i] + a[j] + a[k];
			  
			  if (viz[sum] == 0) /*daca nu am obtinut pana acum suma sum*/
				  {
				   nr++;
				   t[nr].s = sum;
				   t[nr].e1 = a[i];
				   t[nr].e2 = a[j];
				   t[nr].e3 = a[k];
				   
				   viz[sum] = 1;
				  } 
			  
			  if (viz[s - sum] == 1) /*daca am suma opusa cat sa ajung la suma s*/
				  {
				   sort(t+1, t+nr+1, comp);
				   
				   sumc = s - sum;
				   cauta(1, nr);
				   
				   fout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<t[poz].e1<<" "<<t[poz].e2<<" "<<t[poz].e3<<'\n';
				 
				   fout.close();
				   return;
				  }
			 }

 if (gasit == 0)
	 fout<<"-1"<<'\n';

 fout.close();
}


int main()
{
	
 citire();
 solve();
	
 return 0;
}