[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; }
ディスカッション
コメント一覧
まだ、コメントがありません