সমস্যা বিবরণ
কীবোর্ডে ৪টি কী আছে: 'A', 'Ctrl+A' (সিলেক্ট অল), 'Ctrl+C' (কপি), 'Ctrl+V' (পেস্ট)। N সংখ্যক কী-স্ট্রোক দিয়ে সর্বোচ্চ কতটি 'A' প্রিন্ট করা যায় তা বের করতে হবে।
উদাহরণ
N = 7 → আউটপুট: ৯
সিকোয়েন্স: A, A, A, Ctrl+A, Ctrl+C, Ctrl+V, Ctrl+V → ৩ × ৩ = ৯
অ্যালগরিদম: ডাইনামিক প্রোগ্রামিং
dp[n] = n স্ট্রোক দিয়ে সর্বোচ্চ 'A'।
- বেস:
dp[1..6] = 1..6(কপি-পেস্ট দিয়ে লাভ নেই)। n >= 7এর জন্য: ব্রেকপয়েন্টb(৩ থেকে n-3 পর্যন্ত) চুনে:bস্ট্রোক দিয়েdp[b]'A' তৈরি করুন।- বাকি
n - bস্ট্রোক: ২টি স্ট্রোক Ctrl+A, Ctrl+C খাবে, বাকিn - b - 2টি Ctrl+V। - টোটাল =
dp[b] * (n - b - 1)।
- সর্বোচ্চ মান নিন।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
int maxA(int keystrokes) {
if (keystrokes <= 6) return keystrokes;
vector<int> dp(keystrokes + 1);
for (int i = 1; i <= 6; i++) dp[i] = i;
for (int n = 7; n <= keystrokes; n++) {
dp[n] = 0;
for (int b = n - 3; b >= 1; b--) {
int curr = (n - b - 1) * dp[b];
dp[n] = max(dp[n], curr);
}
}
return dp[keystrokes];
}
int main() {
int n = 7;
cout << maxA(n); // আউটপুট: 9
return 0;
}
ইনপুট ও আউটপুট
| ইনপুট | আউটপুট |
|---|---|
7 | 9 |
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(N²) — N = কী-স্ট্রোক সংখ্যা।
- স্থান জটিলতা: O(N) — DP অ্যারে।
