Cod sursa(job #2234048)

Utilizator LorenaMariaHantig Lorena LorenaMaria Data 25 august 2018 11:29:59
Problema Bibel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <iomanip>
using namespace std;
ifstream in("scara2.in");
ofstream out("scara2.out");
int sol[101],solmin[101],uz[101],htot,n,m,h,p,x,nrc;
double ef[101],efmin;
double efort()
{ double x,sum;
  for(int k=1;k<=n;k++)
  { x=sol[k]+ef[k-1];
    sum=sol[k];
    for(int j=2;k-j>=0;j++)
    { sum+=sol[k-j+1];
      if(sum>m)
         break;
      if(sum/j+p+ef[k-j]<x)
         x=sum/j+ef[k-j]+p;
    }
    ef[k]=x;
  }
  return ef[n];
}
void Gen(int k)
{ double x;
  if(k==n+1)
  { if(htot==h)
    { x=efort();
      if(x<efmin && efmin-x>0.001)
      { efmin=x;
        for(int i=1;i<=n;i++)
            solmin[i]=sol[i];
      }
    }
  }
  else
    for(int i=1;i<=h && htot+i<=h && i<=m;i++)
      if(!uz[i])
      { sol[k]=i;
        htot+=i;
        uz[i]=1;
        Gen(k+1);
        uz[i]=0;
        htot-=i;
      }
}
int main()
{ in>>h>>n>>m>>p;
  efmin=(double)h*n+1;
  Gen(1);
  x=efmin;
  while(x>0)
    x/=10,nrc++;
  out<<setprecision(nrc+2)<<efmin<<'\n';
  for(int i=1;i<=n;i++)
    out<<solmin[i]<<' ';
  out<<solmin[n];
  in.close();
  out.close();
  return 0;
}