Cod sursa(job #68602)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 28 iunie 2007 16:43:15
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>

long n, s, v[102],a, b, c,x, ok, nr;

typedef struct
{
  long x, a, b, c;
} numere;

numere A[100000];

void citire()
{
  freopen("loto.in","r",stdin);
  freopen("loto.out","w",stdout);
  scanf("%ld%ld",&n,&s);
  for (int i=1; i<=n; i++)
    scanf("%ld",&v[i]);
}

int pozitie(int p,int u)
{ int st,dr;
  numere aux;
  st=p;dr=u;aux=A[p];
  while(st<dr)
  { while(st<dr && A[dr].x>=aux.x) dr--;
    A[st]=A[dr];
    while(st<dr && A[st].x<=aux.x) st++;
    A[dr]=A[st];
  }
  A[st]=aux;
  return st;
}
void qsort(int p,int u)
{ int m=pozitie(p,u);
  if(p<m) qsort(p,m-1);
  if(m<u) qsort(m+1,u);
}

int cautare(long x)
{
  long p, u, m;
  p=1; u=nr;
  m=(p+u)/2;
  while (p<u)
    {
      if (A[m].x==x) { a=A[m].a; b=A[m].b; c=A[m].c; return 1;}
      else if (A[m].x<x) { p=m; m=(p+u)/2;}
	      else {u=m; m=(p+1)/2;}
    }
  return 0;
}



int main()
{
  citire();

  long i, j, k;
  for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
      for (k=1; k<=n; k++)
	{
	  A[++nr].x=v[i]+v[j]+v[k];
	  A[nr].a=i;
	  A[nr].b=j;
	  A[nr].c=k;
	}
  qsort(1,nr);
  while (A[nr].x>s) nr--;
  for (i=nr; i>=1; i--)
    {
       x=s-A[i].x;
       if (cautare(x))  {printf("%ld %ld %ld %ld %ld %ld",A[i].a, A[i].b, A[i].c, a, b, c); break;}
    }
  if (i==0) printf("-1");
  return 0;
}