Cho số nguyên X, tìm số bước nhảy tối thiểu từ 0 đến X. Bước nhảy đầu tiên là 1 đơn vị, mỗi bước sau dài hơn 1 đơn vị. Có thể nhảy trái hoặc phải. Ví dụ X=8 → 4 bước: 0 → -1 → 1 → 4 → 8.
Quan sát: nếu luôn nhảy phải, sau n bước ở vị trí p = 1+2+...+n. Nếu nhảy trái ở bước k, vị trí p - 2k. Chọn cẩn thận các bước nhảy trái/phải, sau n bước có thể ở bất kỳ điểm nào giữa n(n+1)/2 và -n(n+1)/2 với cùng chẵn/lẻ.
Ví dụ
#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); }
Kết quả
Number of jumps: 5