[AtCoder] ABC 198 C – Compass Walking
問題
方針
原点と \( (X, Y) \) の距離を \( d \) とすると、\( d = \sqrt{X^2 + Y^2} \) であるので、\( d \) が自然数で \( d \bmod R = 0 \) であるとき、
\[ \dfrac{d}{R}\]
が最小の歩数となります。 次に、\( d < R \) であるときを考えると、\( 2 \) 歩で到達できることが分かります。そうではないときを考えます。
原点と \( (X, Y) \) を結ぶ直線上を歩くことを考えます。ここで、\( kR < d < (k + 1)R \) を満たす \( k \) をついて、\( k – 1 \) 歩までこの直線を \( (X, Y)\) に向かって歩いたとすると、\( R < d – (k – 1)R < 2R \) となるので、あと\( 2 \) 歩で到達できることが分かります。したがって、
\[ \left \lceil \dfrac{d}{R} \right \rceil\]
が最小の歩数となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll R, X, Y; cin >> R >> X >> Y; double d = sqrt(X * X + Y * Y); ll l = floor(d); if (floor(d) == ceil(d) && l % R == 0) { cout << l / R << "\n"; } else if (d < R) { cout << 2 << "\n"; } else { cout << l / R + 1 << "\n"; } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません