Cod sursa(job #147682)

Utilizator marinMari n marin Data 3 martie 2008 13:03:08
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <stdio.h>
#define DIM 1001

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

int oka;

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);
void poz(int p);


long int cautB(long int x, long int *v,long int p, long int u);
FILE *g = fopen("loto.out","w");



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];
	pp[m]=m;
      }
  s(x,m);

  for (i=1;(i<=m)&&(x[i]<sum);i++) {
    if ((j=cautB(sum-x[i],x,1,m))!=-1) {
      oka=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;
	}
      }*/

  if (oka==1){
//    for (i=1;i<=6;i++)
//      fprintf(g,"%ld ",w[i]);
    poz(a);
    poz(b);
  }
  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;
      aux = pp[c];
      pp[c] = pp[p];
      pp[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;
      aux = pp[c];
      pp[c] = pp[p];
      pp[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;
    aux = pp[1];
    pp[1] = pp[i];
    pp[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;
}


void poz(int p){
	int c,r;
	c=p/(n*n);   
    r=p%(n*n);
	fprintf(g,"%d ",x[c+(r!=0)]);
	if(r==0)
		fprintf(g,"%d %d ",x[n],x[n]);
	else{
		p=r;
		c=p/n;
		r=p%n;
		fprintf(g,"%d ",x[c+(r!=0)]);
		if(r==0)
			fprintf(g,"%d ",x[n]);
		else
			fprintf(g,"%d ",x[r]);
	}
}