[Codeforces] Educational Codeforces Round 88 (Div. 2) C. Mixing Water

問題

方針

バレットに水を偶数回注いだときのバレットの温度は

\[ \frac{h + c}{2}\]

であり,非負整数 \( n \) を用いて, \( 2n + 1 \) 回水を注いだときのバレットの温度は

\[ \frac{h(n+1) + cn}{2n+1}\]

となります.また,

\[ \frac{h+c}{2} -\frac{h(n+1) + cn}{2n+1}= \frac{c -h}{2(2n+1)} \]

となり,\( c -h < 0\) より,

\[ \frac{h + c}{2} < \frac{h(n+1) + cn}{2n+1}\]

となります.ここで,関数 \( f(n) \) を

\[ f(n) = \frac{h(n+1) + cn}{2n+1}\]

とします.\( f(n) \) について,

\[ f(n) -f(n+1) = \frac{h-c}{(2n+1)(2n+3)}\]

となるので,\( f(n) > f(n+1)\) であり,\( f(n)\) は単調減少であること分かります.

\( t \leq \frac{h+c}{2} \) のとき

このとき,バレットの温度の最小値は

\[ \frac{h+c}{2}\]

であるので,\( 2 \) が答えとなります.

\( t > \frac{h+c}{2} \) のとき

\[ t = \frac{h(n+1) + cn}{2n+1}\]

を \( n \) について解くと

\[ n = \frac{h-t}{2t-h-c}\]

となります.したがって,

\[ m = \left \lfloor \frac{h-t}{2t-h-c} \right \rfloor \]

として,\( |t -f(m)|\) と \( |t -f(m+1)|\) の値を比べます.

ここで,\( g_1 = (2m+1)(2m+3)|t – f(m)| \),\( g_2 = (2m+1)(2m+3)|t-f(m+1)|\) とすれば整数の値で比較することができます.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll h, c, t;

void solve() {
    if (2 * t <= h + c) {
        cout << 2 << "\n";
        return;
    }
    ll n = (h - t) / (2 * t - h - c);
    ll k1 = 2 * n + 1;
    ll k2 = 2 * (n + 1) + 1;
    ll f1 = k1 * k2 * t - k2 * (h * (n + 1) + c * n);
    ll f2 = k1 * k2 * t - k1 * (h * (n + 2) + c * (n + 1));
    if (abs(f1) <= abs(f2)) {
        cout << k1 << "\n";
    } else {
        cout << k2 << "\n";
    }

}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> h >> c >> t;
        solve();
    }
    return 0;
}