Cod sursa(job #139318)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 19 februarie 2008 22:45:57
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main()
{
  long xp, poz, p, saux, ii, jj, kk, i, j, k, n, suma, a[100], s[1000000], nr;
  FILE *f = freopen("loto.in",  "r", stdin),
       *g = 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(a, a+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;
}