Cod sursa(job #179396)

Utilizator lamez0rBogdan Bondor lamez0r Data 15 aprilie 2008 21:16:32
Problema Loto Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<stdio.h>
long s,v[101];
int n;

struct suma {
	    int s,x,y,z;
	    } S[2000];

int pozitie (int s, int d)
    {
    suma aux=S[s];
    while (s<d)
	  {
	  while (s<d&&S[s].s<=S[d].s)
		d--;
	  S[s]=S[d];
	  while (s<d&&S[d].s>=S[s].s)
		s++;
	  S[d]=S[s];
	  }
    S[s]=aux;
    return s;
    }


void quick (int s, int d)
     {
     int p;
     p=pozitie(s,d);
     if (s<p-1)
	quick(s,p-1);
     if (p+1<d)
	quick(p+1,d);
     }


int main ()
{
int i,j,k,poz=0,mij,val,a,b,c;
FILE *f=fopen("loto.in","r");
fscanf(f,"%d%ld",&n,&s);
for (i=1;i<=n;++i)
    fscanf(f,"%d",&v[i]);
fclose(f);
for (i=1;i<=n;++i)
    for (j=i;j<=n;++j)
	for (k=j;k<=n;++k)
	    {
	    S[++poz].s=v[i]+v[j]+v[k];
	    S[poz].x=v[i];
	    S[poz].y=v[j];
	    S[poz].z=v[k];
	    }
quick (1,n);
for (i=1;i<=poz;++i)
    {
    val=s-S[i].s;
    a=i;
    b=poz;
    while (a<=b)
	  {
	  c=(a+b)/2;
	  if (S[c].s==val)
	     {
	     FILE *f=fopen("loto.out","w");
	     fprintf(f,"%d %d %d %d %d %d",S[i].y,S[i].z,S[i].x,S[c].x,S[c].y,S[c].z);
	     fclose(f);
	     return 0;
	     }
	  else
	     if (S[c].s>val)
		b=c-1;
	     else
		a=c+1;
	  }
    }
f=fopen("loto.out","w");
fprintf(f,"-1");
fclose(f);
return 0;
}