C++のゼロから数直線でXに到達するためのジャンプの数を見つけます

整数Xがあるとします。0からXに到達するために必要なジャンプの最小数を見つける必要があります。最初に行われるジャンプの長さは1単位で、連続する各ジャンプの長さは前のジャンプよりも正確に1単位長くなります。各ジャンプで左または右に移動できます。したがって、X =8の場合、出力は4になります。0→-1→1→4→8が可能なステージです。

注意深く観察すれば、それを言うことができます

• 常に正しい方向にジャンプしている場合は、n回ジャンプすると、ポイントp =1 + 2 +3+…+nになります
• 左にジャンプできる場合は、k番目のジャンプでポイントp –2kになります。
• どちらのジャンプを左に、どちらを右にジャンプするかを慎重に選択すると、n回のジャンプの後、n（n + 1）/ 2と–（n *（n + 1）/2の間のポイントになります。 ）、n（n + 1）/2と同じパリティ。

例

#include<iostream>
#include<cmath>
using namespace std;
inline int sumOneToN(int n) {
   return (n * (n + 1)) / 2;
}
int jumps(int n) {
   n = abs(n);
   int ans = 0;
   while (sumOneToN(ans) < n or (sumOneToN(ans) - n) & 1)
      ans++;
   return ans;
}
int main() {
   int n = 9;
   cout << "Number of jumps: " << jumps(n);
}

出力

Number of jumps: 5