Cod sursa(job #1708219)

Utilizator BiancaBMBilteanu Mihaela Bianca BiancaBM Data 26 mai 2016 19:27:59
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 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;
}