Cod sursa(job #138434)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 18 februarie 2008 17:16:34
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>

long s[100];

void qsort(int l, int r)
{
 int aux, i, j, loc;

 i = l; j = r; loc = l;
 while (i < j)
  {
   while ((s[j] >= s[loc]) && (j != loc))
     j--;
   if (j > loc)
     {
       aux  = s[j];
       s[j] = s[loc];
       s[loc] = aux;
       loc  = j;
     }
   while ((s[i] <= s[loc]) && (i != loc))
     i++;
   if (i < loc)
    {
     aux    = s[i];
     s[i]   = s[loc];
     s[loc] = aux;
     loc = i;
    }
  }
 if (l<loc-1)
  qsort(l, loc-1);
 if (loc+1<r)
  qsort(loc+1, r);

}

int main()
{
  FILE *f, *g;
  long suma, saux, ii, jj, kk, l, r, m, i, j, k, nr, n, a[100];

  f = fopen("loto.in", "r");
  g = fopen("loto.out", "w");

  fscanf(f, "%ld %ld", &n, &suma);
  for (i = 1; i <= n; ++i)
    fscanf(f, "%ld", &a[i]);

  nr = 1;
  for (i=1; i <= n; ++i)
    for (j=i; j <= n; ++j)
      for (k=j; k <= n; ++k)
	s[nr++] = a[i] + a[j] + a[k];

  qsort(1, nr-1);

  for (i=1; i <= n; ++i)
    for (j=i; j <= n; ++j)
      for (k=j; k <= n; ++k)
       {
	 saux =   suma - a[i] - a[j] - a[k];
	 if (saux > s[nr-1]) continue;
	 l = 1;
	 r = nr-1;
	 while (l <= r)
	 {
	    m = (l+r) / 2;
	    if (saux == s[m])
	       {
		for (ii=1; ii <= n; ++ii)
		 for (jj=ii; jj <= n; ++jj)
		   for (kk=jj; kk <= n; ++kk)
		     if (a[ii]+a[jj]+a[kk]==saux)
			 {
			    fprintf(g, "%ld %ld %ld %ld %ld %ld", a[i], a[j], a[k], a[ii], a[jj], a[kk]);
			    exit(0);
			 }
	       }
	    else
	      if (saux < s[m])
		r = m-1;
	      else
		l = m+1;
	 }
       }
  fprintf(g, "-1");
  fclose(f);
  fclose(g);

  return 0;
}