ধরুন আমাদের একটি পূর্ণসংখ্যা X আছে। আমাদের 0 থেকে X-এ পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক লাফ খুঁজে বের করতে হবে। প্রথম লাফটি দৈর্ঘ্যের এক ইউনিট হতে পারে এবং প্রতিটি পরপর লাফ দৈর্ঘ্যের আগের লাফের চেয়ে ঠিক এক ইউনিট দীর্ঘ হবে। প্রতিটি লাফে বাম বা ডানদিকে যেতে দেওয়া হয়। তাই যদি X =8, তাহলে আউটপুট হয় 4. 0 → -1 → 1→ 4 → 8 সম্ভাব্য পর্যায়।
যদি আমরা মনোযোগ সহকারে পর্যবেক্ষণ করি, তাহলে আমরা বলতে পারি যে
- যদি আপনি সবসময় সঠিক দিকে ঝাঁপ দেন, তাহলে n লাফ দেওয়ার পরে আপনি বিন্দুতে থাকবেন p =1 + 2 + 3 + … + n
- যদি আমরা বাম দিকেও লাফ দিতে পারি, kth জাম্পে আপনি পয়েন্ট 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
