Cod sursa(job #83233)

Utilizator gigi_becaliGigi Becali gigi_becali Data 10 septembrie 2007 16:06:00
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
using namespace std;
#include <cstdio>
#include <string>
#include <cstdlib>
#include <algorithm>
#define oo 0x3f3f3f3f
#define maxn 666791
#define rnd (rand()-1)
struct nod { int v, a, b,c; nod *l, *r;};

nod *H[maxn], *nil;

typedef nod* tree;
int A, B, C;
int A0, B0, C0;
void init()
{
  srand(time(0));
  nil=new nod;
  nil->v=-oo;
  nil->l=nil->r=0;
  for(int i=0;i<maxn;++i) H[i]=nil;
}



void insert(tree &n, int v)// A, B, C
{
  if(n==nil)
    {
      n=new nod;
      n->v=A+B+C;
      n->a=A;
      n->b=B;
      n->c=C;
      //      n->p=rnd;
      n->l=n->r=nil;
      return;
    }
  if(v<n->v)
    {
      insert(n->l, v);
    }

  if(v>n->v)
    {
      insert(n->r, v);
    }

}

int find(tree n, int v)
{
  if(n==nil)return 0;
  if(v<n->v) return find(n->l, v);
  if(v>n->v) return find(n->r, v);
  if(v==n->v)A0=n->a, B0=n->b, C0=n->b;
  return 1;
}

inline void insrt(int v)
{
  insert(H[v%maxn], v);
}

inline int fnd(int v)
{
  return find(H[v%maxn], v);
}

int main()
{
  int a[101], n, S, i, j, k;
  init();
  freopen("loto.in","r",stdin);
  freopen("loto.out","w",stdout);
  scanf("%d %d\n", &n, &S);
  
  for(i=1;i<=n;++i)scanf("%d ", a+i);

  for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
      for(k=1;k<=n;++k)
	{
	  A=a[i]; B=a[j]; C=a[k];
	  insrt(A+B+C);
	}

  int sol[8];
  for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
      for(k=1;k<=n;++k)
	{
	  if(fnd(S-(a[i]+a[j]+a[k])))
	    {
	      sol[0]=a[i];
	      sol[1]=a[j];
	      sol[2]=a[k];
	      sol[3]=A0;
	      sol[4]=B0;
	      sol[5]=C0;
	      sort(sol, sol+6);
	      for(int k=0;k<6;++k)printf("%d ", sol[k]);
	      printf("\n")
	      return 0;
	    }
	}

  printf("%d\n", -1);
  return 0;
}