Cod sursa(job #60964)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 17 mai 2007 19:46:31
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>

long n, s, v[102], a, b, c, d, e, f, g, ok;

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

int pozitie(int p,int u)
{ int st,dr;
  int aux;
  st=p;dr=u;aux=v[p];
  while(st<dr)
  { while(st<dr && v[dr]>=aux) dr--;
    v[st]=v[dr];
    while(st<dr && v[st]<=aux) st++;
    v[dr]=v[st];
  }
  v[st]=aux;
  return st;
}
void qsort(int p,int u)
{ int m=pozitie(p,u);
  if(p<m) qsort(p,m-1);
  if(m<u) qsort(m+1,u);
}

void parcurs2()
{
  for (a=n; a>=1; a--)
    for (b=n; b>=1; b--)
      for (c=n; c>=1; c--)
	for (d=n; d>=1; d--)
	  for (e=n; e>=1; e--)
	    for (f=n; f>=1; f--)
	      if (v[a]+v[b]+v[c]+v[d]+v[e]+v[f]==s)
		{
		  ok=1;
		  return;
		}
}

void parcurs1()
{
  for (a=1; a<=n; a++)
    for (b=1; b<=n; b++)
      for (c=1; c<=n; c++)
	for (d=1; d<=n; d++)
	  for (e=1; e<=n; e++)
	    for (f=1; f<=n; f++)
	      if (v[a]+v[b]+v[c]+v[d]+v[e]+v[f]==s)
		{
		  ok=1;
		  return;
		}
}

int main()
{
  citire();
  
  if (n<40)  { qsort(1,n); parcurs2();}
    else parcurs1();
  FILE *out=fopen("loto.out","w");
  if (ok)
    fprintf(out,"%ld %ld %ld %ld %ld %ld\n",v[f],v[e],v[d],v[c],v[b],v[a]);
   else fprintf(out,"-1");
  fclose(out);
  return 0;
}