সমস্যা বিবরণ
N পৃষ্ঠার একটি বই দেওয়া আছে। নির্দিষ্ট পৃষ্ঠা K-তে যেতে ন্যূনতম কতবার পৃষ্ঠা পাল্টা করতে হবে তা বের করতে হবে।
- বইয়ের সামনে থেকে (পৃষ্ঠা ১ থেকে) বা পেছন থেকে (পৃষ্ঠা N থেকে) পৃষ্ঠা পাল্টা শুরু করা যায়।
- প্রতিটি পৃষ্ঠার দুপাশ থাকে, ফরন্ট ও ব্যাক। কিন্তু প্রথম পৃষ্ঠার শুধু ব্যাকসাইড থাকে এবং শেষ পৃষ্ঠার শুধু ব্যাকসাইড থাকতে পারে বইয়ের পৃষ্ঠা সংখ্যা অনুযায়ী।
যদি N = 5 এবং K = 4 হয়, তবে ন্যূনতম ১বার পৃষ্ঠা পাল্টা করতে হবে:
- সামনে থেকে শুরু করলে ২বার পাল্টা লাগবে: (1) → (2, 3) → (4,5)
- পেছন থেকে শুরু করলে: (4, 5) ১বার পাল্টা করলেই হবে
সুতরাং, ন্যূনতম পৃষ্ঠা পাল্টা = ১।
এলগরিদম
ফলাফল গণনা করতে নিচের ফর্মুলা ব্যবহার করুন:
1. যদি K জোড় হয়, ফ্রন্ট দূরত্ব = (K - 0)/2 এবং ব্যাক দূরত্ব = (N - 1 - K)/2 2. যদি K বিজোড় হয়, ফ্রন্ট দূরত্ব = (K - 1)/2 এবং ব্যাক দূরত্ব = (N - K)/2
উদাহরণ কোড
#include <iostream>
#include <algorithm>
using namespace std;
int getMinPageTurns(int n, int k) {
if (n % 2 == 0) {
++n;
}
return min((k + 1) / 2, (n - k + 1) / 2);
}
int main() {
int n = 5, k = 4;
cout << "Required page turns = " << getMinPageTurns(n, k) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Required page turns = 1
