Cod sursa(job #2655570)

Utilizator JovanK26Jovan Kascelan JovanK26 Data 4 octombrie 2020 18:55:55
Problema Minim2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("minim2.in");
ofstream fout("minim2.out");
long double eps=1e-10;
int n;
int steps;
long double a,b,r;
int ar[100001];
long double s[100001];
long double power[20001];
long double sum;
int maks=0;
bool check(long double med)
{
   sum=0.0;
   for(int i=n-1;i>=0;i--)
   {
      int le=0;
      int ri=maks-1;
      int m;
      int rez=0;
      long double cur=s[i];
      if(cur-cur*a-med>=eps)
      {
          cur*=a;
          steps++;
      }
      while(le<=ri)
      {
          m=(le+ri)/2;
          long double dif=cur*power[m]-cur*power[m+1];
          if(med-dif>=eps)
          {
              rez=m;
              ri=m-1;
          }
          else
          {
              le=m+1;
          }
      }
      sum+=cur*power[rez];
      steps+=rez;
      if(sum-r>eps)return 0;
   }
   return 1;
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    fin >> n;
    for(int i=0;i<n;i++)
    {
        fin >> ar[i];
    }
    sort(ar,ar+n);
    for(int i=0;i<n;i++)
    {
        s[i]=ar[i];
    }
    fin >> a >> b >> r;
    power[0]=1.0;
    for(int i=1;i<=20000;i++)
    {
        power[i]=power[i-1]*b;
        if(power[i]>eps)
        {
            maks++;
        }
        else
        {
            break;
        }
    }
    long double le=0.0;
    long double ri=1000000000.0;
    long double med;
    long long rez=0;
    for(int i=0;i<1000;i++)
    {
        if(ri-le<=eps)break;
        steps=0;
        med=(le+ri)*0.5;
        if(check(med))
        {
            le=med;
            rez=steps;
        }
        else
        {
            ri=med;
        }
    }
    check(le);
    fout << rez-(int)((r-sum)/le);
    return 0;
}