আমল এবং বিমল পাথরের গেম খেলছে। পাথরগুলো এক সারি আয়োজিত, প্রতিটির মান stoneValue অ্যারেতে। প্রতিটি টার্নে ১, ২ বা ৩টি পাথর নেওয়া যায়। সর্বোচ্চ স্কোর পাওয়া খেলাড় জিতবে। অপ্টিমাল খেলা ধরে "Amal", "Bimal" বা "Tie" রিটার্ন করুন।
উদাহরণ: [1,2,3,7] -> "Bimal"। আমল ৩টি নিলে ৬ পায়, বিমল ৭ পেয়ে জিতবে।
সমাধানের ধাপসমূহ
- DP অ্যারের dp[i] = i-তম পজিশন থেকে খেলাড় যে সর্বোচ্চ নেট স্কোর পারবে।
- Suffix sum অ্যারে sum[i] = i থেকে শেষ পর্যন্ত যোগফল।
- i = n-1 থেকে ০: dp[i] = max(sum[i] - dp[k]) for k = i+1 to i+3।
- total = sum[0], x = dp[0], y = total - x।
- x>y -> "Amal", x==y -> "Tie", অন্যথায় "Bimal"।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string stoneGameIII(vector<int>& v) {
int n = v.size();
vector<int> dp(n+10), sum(n+10);
for (int i = 0; i < n; i++) dp[i] = -1e9;
sum[n-1] = v[n-1];
for (int i = n-2; i >= 0; i--) sum[i] = sum[i+1] + v[i];
for (int i = n-1; i >= 0; i--) {
for (int k = i+1; k <= i+3 && k <= n; k++)
dp[i] = max(dp[i], sum[i] - dp[k]);
}
int total = sum[0], x = dp[0], y = total - x;
return x > y ? "Amal" : (x == y ? "Tie" : "Bimal");
}
};
int main() {
Solution ob;
vector<int> v = {1,2,3,7};
cout << ob.stoneGameIII(v);
return 0;
}
ইনপুট
{1,2,3,7}
আউটপুট
Bimal
