সমস্যা বিবরণ
Nটি খেলোয়াড় একটি টুর্নামেন্টে খেলছে। বিজয়ী কতগুলো খেলা खेलতে পারে তার সর্বোচ্চ সংখ্যা বের করতে হবে। এই টুর্নামেন্টে দুজন খেলোয়াড় একে অপরের সাথে খেলতে পারবে শুধু তখন যখন তাদের খেলা সংখ্যার পার্থক্য ১-এর চেয়ে বেশি নয়।
উদাহরণ
যদি ৩জন খেলোয়াড় থাকে তবে বিজয়ী নির্ধারণের জন্য ২টি খেলা লাগবে নিচেরভাবে −
খেলা – ১: খেলোয়াড় ১ vs খেলোয়াড় ২
খেলা - ২: খেলোয়াড় 2 vs খেলা - ১ এর বিজয়ী
অ্যালগরিদম
- এই সমস্যাটি আমরা সমাধান করতে পারি প্রথমে ন্যূনতম কতজন খেলোয়াড় দরকার যাতে বিজয়ী x সংখ্যক খেলা খেলে। একবার এটি বের হয়ে গেলে মূল সমস্যা শুধু এর বিপরীত। ধরুন dp[i] হলো ন্যূনতম খেলোয়াড় সংখ্যা যাতে বিজয়ী i সংখ্যক খেলা খেলে
- dp মানগুলোর মধ্যে একটি রিকার্সিভ রিলেশন লিখা যায়: dp[i + 1] = dp[i] + dp[i – 1] কারণ যদি রানার-আপ (i – 1) সংখ্যক খেলা খেলে এবং বিজয়ী i সংখ্যক খেলা খেলে এবং যেসব খেলোয়াড়ের সাথে তারা খেলেছে সেগুলো আলাদা হয়, তবে বিজয়ীর মোট খেলা সংখ্যা সেই দুটি সেটের যোগফল হবে।
- উপরোক্ত রিকার্সিভ রিলেশনটি লেখা যায়: dp[i] = dp[i – 1] + dp[i – 2] যা ফিবোনাচ্চি সিরিজের রিলেশনের সাথে একই, তাই আমাদের চূড়ান্ত উত্তর হবে ইনপুটে দেওয়া খেলোয়াড় সংখ্যার চেয়ে ছোট বা সমান সর্বোচ্চ ফিবোনাচ্চি সংখ্যার ইনডেক্স।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int getMaxGamesToDecideWinner(int n) { int dp[n]; dp[0] = 1; dp[1] = 2; int idx = 2; do { dp[idx] = dp[idx - 1] + dp[idx - 2]; } while(dp[idx++] <= n); return (idx - 2); } int main() { int players = 3; cout << "Maximum games required to decide winner = " << getMaxGamesToDecideWinner(players) << endl; return 0; }আউটপুট
প্রোগ্রামটি কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে −
Maximum games required to decide winner = 2
