Cod sursa(job #172684)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 6 aprilie 2008 17:26:13
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<fstream>
using namespace std;
long long sum[1000001][4],l,ll;
void recons_heap(long long i)
{
long long maxim,lef,r;
maxim=i;
lef=2*i;
r=2*i+1;
if (lef<=ll&&sum[lef][0]>sum[maxim][0]) maxim=lef;
if (r<=ll&&sum[r][0]>sum[maxim][0]) maxim=r;
if (maxim!=i)
  {
	long long aux;
	aux=sum[maxim][0];
	sum[maxim][0]=sum[i][0];
	sum[i][0]=aux;
	aux=sum[maxim][1];
	sum[maxim][1]=sum[i][1];
	sum[i][1]=aux;
	aux=sum[maxim][2];
	sum[maxim][2]=sum[i][2];
	sum[i][2]=aux;
	aux=sum[maxim][3];
	sum[maxim][3]=sum[i][3];
	sum[i][3]=aux;
	recons_heap(maxim);
  }
}

void cons_heap()
{
long long i;
for (i=ll/2;i>=1;i--) recons_heap(i);
}

void heap_s()
{
long long i;
cons_heap();
for (i=ll;i>=2;i--)
   {
	long long aux;
	aux=sum[1][0];
	sum[1][0]=sum[i][0];
	sum[i][0]=aux;
	aux=sum[1][1];
	sum[1][1]=sum[i][1];
	sum[i][1]=aux;
	aux=sum[1][2];
	sum[1][2]=sum[i][2];
	sum[i][2]=aux;
	aux=sum[1][3];
	sum[1][3]=sum[i][3];
	sum[i][3]=aux;
    ll--;
	recons_heap(1);
   }
}
int main()
{
long long i,n,s,st[10],k,v[105],j;
ifstream f("loto.in");
ofstream g("loto.out");
f>>n>>s;
for (i=1;i<=n;i++) f>>v[i];
/*k=1;
st[k]=0;
while (k)
     {
     st[k]++;
     if (st[k]<=n)
       {
       if (k==3)
	 {

	 sum[++l][0]=v[st[1]]+v[st[2]]+v[st[3]];
	 sum[l][1]=v[st[1]];
	 sum[l][2]=v[st[2]];
	 sum[l][3]=v[st[3]];
	 }
       else
	 {
	 k++;
	 st[k]=0;
	 }
       }
     else k--;
     }*/
for (i=1;i<=n; i++)
	for (j=i;j<=n;j++)
		for (k=j;k<=n;k++) 
		{
		sum[++l][0]=v[i]+v[j]+v[k];
		sum[l][1]=v[i];
		sum[l][2]=v[j];
		sum[l][3]=v[k];
		}
ll=l;
heap_s();
long long caut,ok=1,a,b,mij,x[7];
ok=1;
for (i=1;i<=l&&ok;i++)
    if (s>=sum[i][0])
    {
	caut=s-sum[i][0];
	a=1;
	b=l;
	ok=1;
	while (a<=b&&ok)
	     {
	      mij=(a+b)/2;
          if (sum[mij][0]==caut) 
		      {
			  x[1]=sum[i][1];x[2]=sum[i][2];x[3]=sum[i][3];x[4]=sum[mij][1];x[5]=sum[mij][2];x[6]=sum[mij][3];
			  long long aux,ca;
			  do 
			  {
				  ca=0;
				  for (j=1;j<6;j++) if (x[j]>x[j+1])
				                      {
									   aux=x[j];
									   x[j]=x[j+1];
									   x[j+1]=aux;
									   ca=1;
									   }
			  } while (ca);
			  for (j=1;j<=6;j++) g<<x[j]<<' ';
			  
			  ok=0;
		      }		
		  if (sum[mij][0]>caut) b=mij-1;
                  else a = mij+1;  
		  //if (sum[mij][0]<caut) a=mij+1;
	      }
    }

if (ok) g<<"-1\n";
f.close();
g.close();
return 0;
}