Cod sursa(job #127637)

Utilizator marinMari n marin Data 24 ianuarie 2008 18:58:41
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <stdio.h>
#define DIM 1000001

long int n,i,t,j,k,m,sum,a,b;
long int v[101];
long int x[DIM];
long int w[7];


void cit(long int *v, long int &n);
void cre(long int *v, long int n);
void corect(long int poz, long int *v, long int n);
void s(long int *v, long int n) ;
void af(long int *v, long int n);
int ver(long int *v, long int n);

long int cautB(long int x, long int *v,long int p, long int u);



int main(){
  FILE *f = fopen("loto.in","r");
  fscanf(f,"%ld %ld",&n,&sum);
  for (i=1;i<=n;i++)
    fscanf(f,"%ld",&v[i]);
  fclose(f);
  t=0;
  for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
      for (k=1;k<=n;k++)
	x[++m] = v[i]+v[j]+v[k];
  s(x,m);
  for (i=1;(i<=m)&&(x[i]<sum);i++) {
    if ((j=cautB(sum-x[i],x,1,m))!=-1) {
      break;
    }
  }

  a=i;
  b=j;

  int oka=0;
  int okb=0;
  for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
      for (k=1;k<=n;k++) {
	if (v[i]+v[j]+v[k] == x[a]) {
	  w[1]=v[i];w[2]=v[j];w[3]=v[k];
	  oka=1;
	}
	if (v[i]+v[j]+v[k] == x[b]) {
	  w[4]=v[i];w[5]=v[j];w[6]=v[k];
	  okb=1;
	}
      }
  FILE *g = fopen("loto.out","w");
  if (oka+okb==2){
    for (i=1;i<=6;i++)
      fprintf(g,"%ld ",w[i]);
  }
  else
    fprintf(f,"-1");
  fclose(g);
  return 0;

}


long int cautB(long int x,long int *v,long int p, long int u){
  long int m;
  while (p<=u) {
    m=(p+u)/2;
    if (v[m]==x) return m;
    else
      if (v[m]>x) u=m-1;
      else p=m+1;
  }
  return -1;
}



void cit(long int *v, long int &n){
  long int i;
  FILE *f = fopen("date.in","r");
  fscanf(f,"%ld",&n);
  for (i=1;i<=n;i++)
    fscanf(f,"%ld",&v[i]);
  fclose(f);
}


void cre(long int *v, long int n){
  long int i,aux,c,p;
  for (i=2;i<=n;i++) {
    c = i;
    p = i>>1;
    while ((p)&&(v[c]>v[p])) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      c = p;
      p = p>>1;
    }
  }
}

void corect(long int poz, long int *v, long int n){
  long int aux,p,c;
//  aux = v[1];
//  v[1] = v[i];
//  v[i] = aux;
  p = poz;
  c = p<<1;
  while (c<=n) {
    if ((c+1<=n) && (v[c+1]>v[c]))
      c++;
    if (v[c]>v[p]) {
      aux = v[c];
      v[c] = v[p];
      v[p] = aux;
      p = c;
      c = p<<1;
    } else break;
  }

}

void s(long int *v, long int n) {
  long int i,aux,p,c;
  cre(v,n);
  for (i=n;i>1;i--) {
    aux = v[1];
    v[1] = v[i];
    v[i] = aux;
    corect(1,v,i-1);
  }
}

void af(long int *v, long int n){
  long int i;
  FILE *g = fopen("date.out","w");

  for (i=1;i<=n;i++)
    fprintf(g,"%ld\n",v[i]);
  fprintf(g,"\n");
  fclose(g);
}

int ver(long int *v, long int n){
  long int i;
  for (i=1;i<n;i++)
    if (v[i]>v[i+1]){
      printf("%ld",i);
      return 0;
    }
  return 1;
}