สมมติว่าเรามีจำนวนเต็ม X เราต้องหาจำนวนการกระโดดขั้นต่ำที่จำเป็นในการไปถึง X จาก 0 การกระโดดครั้งแรกสามารถมีความยาวได้หนึ่งหน่วย และการกระโดดแต่ละครั้งจะยาวกว่าการกระโดดครั้งก่อนหนึ่งหน่วย อนุญาตให้ไปทางซ้ายหรือขวาในการกระโดดแต่ละครั้ง ดังนั้นหาก 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
