Yukicoder051 やる気の問題

問題概要

Thomasのやる気は、簡単に計算できる。

締め切りまでの残りの日数を$D$日とし、 残りの作業量を$W$とすると その日のやる気は$\displaystyle \frac{W}{D^2}$となる。 そして、やる気の小数切り捨ての値が、その日の作業量になる。

Thomasは、最終日にどれだけ作業をしないといけなくなるかが気になっている。

最初の日に与えられた作業量$W$と締め切りまでの日数$D$が与えられるので あなたは、Thomasが最後の日にどれだけの作業量があるか計算してあげてください。

$W,D\leqq10^5$

yukicoder051

解法

次の日の作業量が負になることはないので、シュミレーションしていくだけで良い。

計算量:$O(D)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    LL W, D;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> W >> D;
        FOR(d, 0, D) {
            LL w = W / (D - d) / (D - d);
            W -= w;
            if (d == D - 1)ans = w;
    
        }
        cout << ans << "\n";
    
        return 0;
    }