Cod sursa(job #70555)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 6 iulie 2007 13:38:02
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<stdio.h>

int n,o,e;
long a[101],q[6],s,max;

void citire()
{
freopen("loto.in","r",stdin);
scanf("%d%ld", &n, &s);
for (int i=0; i<n; i++)
    {
	scanf("%ld", &a[i]);
    if (a[i]>max)
       max=a[i];
    }
fclose(stdin);
}

void radx(long max,long zero[101],long n)
{
long z,u,j;
int unu[101];
for (long i=0; i<max; i++)
    {
    z=-1;
    u=-1;
    for (j=0; j<n; j++)
	{
	if (((zero[j] >> i) &1)==0)
	   zero[++z]=zero[j];
	   else unu[++u]=zero[j];
	}
    u=-1;
    for (j=z+1; j<n; j++)
	zero[j]=unu[++u];
    }
}

int nr_pasi(long max1)
{
int pas=0;
while (max1>0)
      {
      ++pas;
      max1>>=1;
      }
return pas;
}

void scrie()
{
freopen("loto.out","w",stdout);
for (int i=0; i<6; i++)
    printf("%ld ",q[i]);
fclose(stdin);
o=1;
}

void cautare(int st,int dr)
{
int p=(st+dr)/2,l=0;
if (a[p]<=s)
   e=(st+dr)/2;
   else if (a[(st+dr)/2]>s)
	   cautare(st,(st+dr+1)/2);
	else cautare((st+dr-1)/2,dr);
}

void back(int w)
{
if (w<0)
   {
   if (s==0)
      scrie();
   }
   else {
	if (s>0)
	   {
	cautare(0, n-1);
	while (a[e+1]<s && e+1<=n-1)
	      e++;
	for (int i=e; i>=0; i--)
	    {
	    if (a[i]<=s)
	       {
	       s-=a[i];
	       q[w]=a[i];
	       back(w-1);
	       s+=a[i];
	       if (o==1)
		  break;
	       }
	    }}
	}
}

int main()
{
citire();
o=0;
max=nr_pasi(max);
radx(max,a,n);
back(5);
freopen("loto.out","w",stdout);
if (o==0)
   printf("-1");
   else {
	for (int i=0; i<6; i++)
	    printf("%ld ",q[i]);
	}
fclose(stdin);
return 0;
}