Competitive Programming Solutions

1476B - Inflation

29 Jan 2021 — Tags: greedy — URL

The problem tells us that for each $i > 0$ we need:

\[\frac{p_i}{psum_{i- 1}} \leq \frac{k}{100}\]

Where $psum_{i}$ is the prefix sum of $p$ up to $i$.

To avoid floating errors, we want the following condition:

\[\frac{100 p_i}{k} \leq psum_{i-1}\]

Furthermore, note that it is always optimal to increment $p_0$, as it will necessarily decrease all inflation rates.

So, for each $i$ we can greedily try to increase $p_0$ until the condition holds.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll ceil(ll a, ll b) { return (a + b - 1) / b; }
ll solve(vector<ll> p, int k)
{
    int n = p.size();
    ll sum = p.front(), ans = 0;
    for (int i = 1; i < n; ++i)
    {
        ll dif = ceil(100 * p[i], k) - (sum + ans);
        if (dif > 0)
            ans += dif;
        sum += p[i];
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vector<ll> p(n);
        for (auto &pi : p)
            cin >> pi;
        cout << solve(p, k) << endl;
    }
    return 0;
}

Related posts