Cod sursa(job #3238094)

Utilizator AndrijaMladAndrija Mladenovikj AndrijaMlad Data 19 iulie 2024 01:25:35
Problema Minim2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

long double eps=1e-10;
const int maxn=100001;
const int mod=1e9+7;
const int logn=25;

int n;
int ar[maxn];
int steps;
long double a,b,r;
long double s[maxn];
long double power[maxn];
long double sum;
int mx=0;

bool f(long double mid)
{
   sum=0.0;
   for(int i=n-1;i>=0;i--)
   {
      int l=0;
      int r=mx-1;
      int m;
      int ans=0;
      long double cur=s[i];
      if(cur-cur*a-mid>=eps)
      {
          cur*=a;
          steps++;
      }
      while(l<=r)
      {
          m=(l+r)/2;
          long double dif=cur*power[m]-cur*power[m+1];
          if(mid-dif>=eps)
          {
              ans=m;
              r=m-1;
          }
          else
          {
              l=m+1;
          }
      }
      sum+=cur*power[ans];
      steps+=ans;
      if(sum-r>eps)return 0;
   }
   return 1;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("minim2.in","r",stdin);
    freopen("minim2.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    sort(ar,ar+n);
    for(int i=0;i<n;i++)
    {
        s[i]=ar[i];
    }
    cin>>a>>b>>r;
    power[0]=1.0;
    for(int i=1;i<=20000;i++)
    {
        power[i]=power[i-1]*b;
        if(power[i]>eps)
        {
            mx++;
        }
        else
        {
            break;
        }
    }
    long double l=0.0;
    long double r=1000000000.0;
    long double mid;
    long long ans=0;
    for(int i=0;i<1000;i++)
    {
        if(r-l<=eps)break;
        steps=0;
        mid=(l+r)*0.5;
        if(f(mid))
        {
            l=mid;
            ans=steps;
        }
        else
        {
            r=mid;
        }
    }
    return 0;
}