[Codeforces] Codeforces Round #614 (Div. 2) B. JOE is on TV!

2020年1月20日2020年12月15日

問題

方針

\( i \) 回目の質問で脱落する人数を \( a_i \) とし、\( a_i \) の累積和 \( s_i \) を \( s_i = a_1 + a_2 + \cdots a_i \) とします。このとき、得られる賞金は、

\[ \dfrac{a_1}{n} + \dfrac{a_2}{n – s_1} + \dfrac{a_3}{n – s_2} + \cdots + \dfrac{a_{i – 1}}{n – s_i}\]

となります。このとき、\( a_j = 1 \ ( 1 \leq j \leq n) \) のとき最大となります。例えば、\( a_1 = 2 \) とすると、

\[ \dfrac{2}{n} = \dfrac{1}{n} + \dfrac{1}{n} < \dfrac{1}{n} + \dfrac{1}{n – 1}\]

となるので、不適であることが分かります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    double ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (double) 1 / i;
    }
    cout << ans << "\n";
    return 0;
}