Cod sursa(job #2349309)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 20 februarie 2019 12:56:59
Problema Minim2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<bits/stdc++.h>
#define eps 1e-6
#define Nmax 100010
using namespace std;
ifstream f("minim2.in");
ofstream g("minim2.out");
int n;
double dist[Nmax], p[Nmax / 10 + 10], a, b, r;
int itt;
int pz;
bool check(double c)
{
    ++pz;
    double timp = 0.00000;
    for(int i = n; i >= 1; --i)
    {
        int st = 0;
        int dr = 10000;
        int ans = 0;
        while(st <= dr)
        {
            int mid = (st + dr) / 2;
            double diff = dist[i] * p[mid] - dist[i] * p[mid + 1];
            if(diff <= c)
                ans = mid, dr = mid - 1;
            else
                st = mid + 1;
        }
        timp = timp + dist[i] * p[ans];
        itt += ans;
        if(timp > r)
            return 0;
    }
    return 1;
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> dist[i];
    sort(dist + 1, dist + n + 1);
    f >> a >> b >> r;
    p[0] = 1.0000;
    for(int i = 1; i <= 10001; ++i)
        p[i] = p[i-1] * b;
    double sum = 0;
    for(int i = 1; i <= n; ++i)
        sum += dist[i];
    if(r - sum >= -eps)
    {
        g << 0;
        return 0;
    }
    dist[n] *= a;
    int ans = 0;
    sort(dist + 1, dist + n + 1);
    double st = 0.0000;
    for(int i = 1; i <= n; ++i)
        st = max(st, dist[i] * p[10000] - dist[i] * p[10001]);
    double dr = 500000000.0000;
    for(int i = 1; i <= 1000; ++i)
    {
        if(dr - st <= eps)
            break;
        itt = 0;
        double mid = (st + dr) * 0.500000;
        if(check(mid))
            st = mid, ans = itt;
        else
            dr = mid;
      //  g << mid << " " << itt << '\n';
    }
    g << ans;
    return 0;
}