Cod sursa(job #519629)

Utilizator Smaug-Andrei C. Smaug- Data 6 ianuarie 2011 00:41:14
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <cstdlib>

#define MAXN 101

struct sum {
  int val;
  int a, b, c;
};

int compare(const void *a, const void *b){
  return (((sum*)a)->val-((sum*)b)->val);
}

int main(){

  freopen("loto.in", "r", stdin);
  freopen("loto.out", "w", stdout);

  int N, S, loto[MAXN], spos, found=0;
  int left, right, mid, key;
  int i, j, k;
  sum V[MAXN*MAXN*MAXN];

  scanf("%d%d", &N, &S);
  for(i=0; i<N; i++)
    scanf("%d", loto+i);

  spos=0;
  for(i=0; i<N; i++)
    for(j=0; j<N; j++)
      for(k=0; k<N; k++){
	V[spos].val=loto[i]+loto[j]+loto[k];
	V[spos].a=loto[i]; V[spos].b=loto[j]; V[spos].c=loto[k];
	spos++;
      }
	
  qsort(V, spos, sizeof(sum), compare);
  
  for(i=0; i<spos && !found; i++){
    key=S-V[i].val; left=1; right=spos-1;
    while(left <= right){
      mid=((right-left)>>1)+left;
      if(key == V[mid].val){
	printf("%d %d %d %d %d %d", V[i].a, V[i].b, V[i].c, V[mid].a, V[mid].b, V[mid].c);
	found=1;
	break;
      } else if(key<V[mid].val){
	right=mid-1;
      } else {
	left=mid+1;
      }
    }   
  }

  if(!found)
    printf("%d\n", -1);

  return 0;

}