Cod sursa(job #68606)

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

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

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

numere A[1000000];

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

void buble()
{
  int i, j, ok=1, aux;
  while (ok)
   {
     ok=0;
     for (i=1; i<6; i++)
       if (sol[i]>sol[i+1])
	   {
	     aux=sol[i];
	     sol[i]=sol[i+1];
	     sol[i+1]=aux;
	     ok=1;
	   }
   }
}



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))  { sol[1]=A[i].a; sol[2]=A[i].b; sol[3]=A[i].c;
			  sol[4]=a; sol[5]=b; sol[6]=c;break;}
    }


  if (i==0) printf("-1");
    else
      {
      //buble();
      for (i=1; i<=6; i++)
	printf("%ld ",sol[i]);
      }

  return 0;
}