Cod sursa(job #16034)

Utilizator adalLica Adela adal Data 11 februarie 2007 23:05:08
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
//program loto

#include <stdio.h>

struct rec
{
  long t,x,y,z;
} b[1000005], s[1000005];
long a[105],i,j,n,k,xx,sum;
FILE *f=fopen("loto.in","r");
FILE *g=fopen("loto.out","w");

void interclas(long st,long m, long dr)
{
  long i,t, j,k;
  for (i=st; i<=dr; i++) b[i]=s[i];
  i=st; j=m+1; k=st;
  while ((i<=m)&&(j<=dr))
    if (b[i].t>b[j].t) { s[k]=b[j]; j++; k++; }
    else { s[k]=b[i]; i++; k++; }
 for (t=i; t<=m; t++)
 {   s[k]=b[t]; k++; }

 for (t=j; t<=dr; t++)
 { s[k]=b[t]; k++; }
}

void mergesort(long st, long dr)
{
 long m;
 if (st<dr)
 {
    m=(st+dr)/2;
    mergesort(st,m);
    mergesort(m+1, dr);
    interclas(st,m,dr);
  }
}
int main()
{
  long mn;
  fscanf(f,"%ld %ld\n", &n, &sum);
  mn=0; 
  for (i=1; i<=n; i++) fscanf(f,"%ld", &a[i]);
  for (i=1; i<=n; i++)
   for (j=i; j<=n; j++)
     for (k=j; k<=n; k++)
     {
	 s[++mn].t=a[i]+a[j]+a[k];
	 s[mn].x=a[i]; s[mn].y=a[j]; s[mn].z=a[k];
     }
   mergesort(1,mn); j=mn;  xx=0;
   i=1;
   while((i<=mn)&&(xx==0))
   {
     while (((s[j].t+s[i].t)>sum)&& (j>=1)) j--;
     if (j>0) if ((s[j].t+s[i].t)==sum) {
	fprintf(g,"%ld %ld %ld %ld %ld %ld\n", s[i].x,s[i].y,s[i].z,s[j].x,s[j].y,s[j].z);
	xx=-1;
      }
      i++;
    }
    if (xx==0) fprintf(g,"%ld\n",-1);
   return 0;
}