[Codeforces] Educational Codeforces Round 99 (Div. 2) B. Jumps
問題
方針
\( t \) 回のジャンプで行くことができる最大の点は
\[\dfrac{t(t + 1)}{2}\]
となります。ここで、自然数 \( t \) を
\[ \dfrac{t(t + 1)}{2} \geq x\]
を満たす最小の \( t \) とします。このとき今いる座標がちょうど \( x \) となれば答えは \( t \) となります。以降は、
\[ \dfrac{t(t + 1)}{2} > x\]
の場合を考えます。ここで、\( t \) 回のジャンプのどれかで \( 1 \) 戻るジャンプに入れ替えることを考えます。\( v \) 回目のジャンプを入れ替えるとすると、座標は
\[ \dfrac{t(t + 1)}{2} – v – 1\]
となります。したがって、
\begin{eqnarray}
\dfrac{t(t + 1)}{2} – v – 1 &=& x\\
v &=& \dfrac{t(t + 1) – 2x – 2}{2}
\end{eqnarray}
となります。したがって、\( v \geq 1 \) ならば、答えは \( t \) となります。ここで、\( t(t + 1) \) は \( 2 \) の倍数なので、
\[ t(t + 1) – 2x – 2 = 0 \]
のときを考えます。このとき、
\[ \dfrac{t(t + 1)}{2} – x = 1\]
なので、\( 1 \) 戻るジャンプを新たにすれば、\( x \) に到達するので答えは \( t + 1 \) となります。
また、\( t \) 回のジャンプの中で \( 2 \) つのジャンプを \( 1 \) 戻るジャンプに入れ替えることを考えると、
\[ \dfrac{t(t + 1)}{2} – (v + 1) – (w + 1) = x\]
という方程式を考えることになりますが、\( z = v + w \) と置き換えて考えると、無駄な操作であることが分かります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int bs(int x) { int l = 0; int r = 10000; while (r - l > 1) { int m = l + (r - l) / 2; if ((m * (m + 1)) / 2 >= x) { r = m; } else { l = m; } } return r; } int main() { int t, x; cin >> t; for (int i = 0; i < t; i++) { cin >> x; int t = bs(x); int e = t * (t + 1) - 2 * x - 2; if (t * (t + 1) == 2 * x || (e / 2 >= 1)) { cout << t << "\n"; } else { cout << t + 1 << "\n"; } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません