Cod sursa(job #140605)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 22 februarie 2008 00:07:30
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <stdio.h>   
#include <stdlib.h>  
#include <algorithm> 

using namespace std;
  
long s[1000000];   
  
void qsort(int l, int r)   
{   
 int aux, i, j, x, 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];   
  
  sort(s+1, s+nr);
  
  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];   
     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;   
}