मान लीजिए "100 गेम" नामक एक गेम में, दो खिलाड़ी बारी-बारी से रनिंग टोटल में 1 से 10 तक का कोई भी इंटीजर जोड़ते हैं। जो खिलाड़ी पहले रनिंग टोटल को 100 तक पहुंचाता है या उससे अधिक करता है, वह जीतता है। तो क्या होगा अगर हम गेम को इस तरह बदल दें कि खिलाड़ी इंटीजर्स को दोबारा उपयोग न कर सकें?
उदाहरण के लिए, अगर दो खिलाड़ी 1..15 के कॉमन पूल से नंबर्स निकालते हैं बिना रिप्लेसमेंट के जब तक वे टोटल >= 100 तक नहीं पहुंच जाते।
तो मान लीजिए दिए गए इंटीजर maxChoosableInteger और एक अन्य इंटीजर desiredTotal, निर्धारित करें कि पहला खिलाड़ी जो चलता है वह जीत को फोर्स कर सकता है या नहीं, यह मानते हुए कि दोनों खिलाड़ी ऑप्टिमली खेलते हैं।
हम हमेशा मान सकते हैं कि maxChoosableInteger 20 से बड़ा नहीं होगा और desiredTotal 300 से बड़ा नहीं होगा। उदाहरण के लिए, अगर इनपुट maxChoosableInteger = 20 है, और desiredTotal 11 है, तो रिजल्ट false होगा। चाहे पहला खिलाड़ी कुछ भी चुने, पहला खिलाड़ी हार जाएगा।
इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:
साइज 2^21 का एक ऐरे dp बनाएं
solve() नाम का एक मेथड डिफाइन करें, जो n, s, और mask लेगा।
अगर s <= 0, तो false लौटाएं
अगर dp[mask] -1 नहीं है, तो dp[mask] लौटाएं
ret := false सेट करें
i को 1 से n तक लूप करें:
अगर (mask को i बिट्स राइट शिफ्ट करना) ऑड है, तो:
ret := ret OR (solve(n, s - i, mask XOR 2^i) का इनवर्स)
dp[mask] := ret
ret लौटाएं
मेन मेथड से, निम्न करें:
अगर desiredTotal <= 0, तो true लौटाएं
i को 0 से 2^21 तक लूप करें: dp[i] := -1
अगर desiredTotal > (पहले n नंबर्स का योग), तो false लौटाएं
solve(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);
}
};
int main() {
Solution ob;
cout << (ob.canIWin(10,11));
}
इनपुट
10 11
आउटपुट
0
