ধরুন "100 গেমস" নামক একটি গেমে দুইজন খেলোয়াড় পালাক্রমে যোগ করে, একটি চলমান মোটে, 1 থেকে 10 পর্যন্ত যেকোনো পূর্ণসংখ্যা। যে খেলোয়াড় প্রথমে রানিং টোটালে পৌঁছায় বা 100 ছাড়িয়ে গেলে সে জিতবে। তাহলে কী হবে যদি আমরা গেমটি পরিবর্তন করি যাতে খেলোয়াড়রা পূর্ণসংখ্যা পুনরায় ব্যবহার করতে না পারে?
উদাহরণস্বরূপ, যদি দুইজন খেলোয়াড় 1..15 সংখ্যার একটি সাধারণ পুল থেকে প্রতিস্থাপন ছাড়াই পালা অঙ্কন করে যতক্ষণ না তারা মোট>=100 এ পৌঁছায়।
তাই ধরুন, একটি পূর্ণসংখ্যা maxChoosableInteger এবং অন্য একটি পূর্ণসংখ্যা কাঙ্ক্ষিত মোট দেওয়া হয়েছে, উভয় খেলোয়াড়ই সর্বোত্তমভাবে খেলবে বলে ধরে নিয়ে, স্থানান্তরিত প্রথম খেলোয়াড় একটি জয়ে বাধ্য করতে পারে কিনা তা নির্ধারণ করুন।
আমরা সর্বদা ধরে নিতে পারি যে maxChoosableInteger 20-এর মানের থেকে বড় হবে না এবং কাঙ্খিত মোট 300-এর চেয়ে বড় হবে না। তাই যদি ইনপুটটি maxChooseableInteger =20 হয় এবং কাঙ্খিত মোট 11 হয়, তাহলে ফলাফল মিথ্যা হবে। প্রথম খেলোয়াড় যেই পছন্দ করুক না কেন, প্রথম খেলোয়াড় হারবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
2^21 আকারের dp নামে একটি অ্যারে তৈরি করুন
-
একটি পদ্ধতি সংজ্ঞায়িত করুন সমাধান(), এটি n, s, এবং মাস্ক লাগবে।
-
যদি s <=0 হয়, তাহলে মিথ্যা ফেরত দিন
-
যদি dp[mask] -1 না হয়, তাহলে dp[mask]
ফেরত দিন -
সেট ret :=মিথ্যা
-
আমি 1 থেকে n
এর মধ্যে-
যদি (মাস্ক আমি ডানদিকে বিট করে) বিজোড় হয়, তাহলে
-
ret :=ret OR (সল্ভ (n, s – i, মাস্ক XOR 2^i) এর বিপরীত)
-
-
-
dp[মাস্ক] :=ret
-
রিটার্ন রিটার্ন
-
মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
-
যদি ইচ্ছা হয় মোট <=0, তাহলে সত্য ফেরত দিন
-
আমি 0 থেকে 2^21
রেঞ্জে-
dp[i] :=-1
-
-
যদি ইচ্ছা হয় মোট> (প্রথম n সংখ্যার যোগফল), তারপর মিথ্যা ফেরত দিন
-
রিটার্ন সমাধান(n, desiredTotal, 0)
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[1 << 21];
bool solve(int n, int s, int mask){
if(s <= 0) return false;
if(dp[mask] != -1) return dp[mask];
bool ret = false;
for(int i = 1; i <= n; i++){
if(!((mask >> i) & 1)){
ret |= (!solve(n, s - i, (mask ^ (1 << i))));
}
}
return dp[mask] = ret;
}
bool canIWin(int n, int desiredTotal) {
if(desiredTotal <= 0) return true;
for(int i = 0; i < (1 << 21); i++)dp[i] = -1;
if(desiredTotal > (n * (n + 1)/ 2))return false;
return solve(n, desiredTotal, 0);
}
};
main() {
Solution ob;
cout << (ob.canIWin(10,11));
} ইনপুট
10 11
আউটপুট
0
