Cod sursa(job #139337)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 19 februarie 2008 23:17:37
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

long xp, poz, p, saux, ii, jj, kk, i, j, k, n, suma, a[100], s[1000000], nr;

int main()
{
  freopen("loto.in",  "r", stdin),
  freopen("loto.out", "w", stdout);
  
  scanf("%ld %ld", &n, &suma);
  for ( i = 1; i <= n; ++i)
    scanf("%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];
  nr--;

  sort(s, s+nr);
    
  for ( p = 1; p < nr; p <<= 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];
	     xp = p;
	     for ( poz = 0; xp; xp >>= 1)
	       if ( poz+xp <= nr && s[poz+xp] <= saux)
	        poz += xp;
         if ( s[poz] == saux)
           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) 
		           {
		             printf("%ld %ld %ld %ld %ld %ld", a[i], a[j], a[k], a[ii], a[jj], a[kk]);
		             exit(0);
		           }
       }

  printf("-1");

  return 0;
}