क्या मैं C++ में जीत सकता हूँ?

मान लीजिए कि "100 गेम" नामक गेम में दो खिलाड़ी बारी-बारी से 1 से 10 तक के किसी भी पूर्णांक को रनिंग टोटल में जोड़ते हैं। वह खिलाड़ी जो पहले रनिंग टोटल तक पहुंचता है या 100 से अधिक, वह जीतता है। तो क्या हुआ अगर हम खेल को बदल दें ताकि खिलाड़ी पूर्णांकों का पुन:उपयोग न कर सकें?

उदाहरण के लिए, यदि दो खिलाड़ी 1..15 की संख्याओं के एक सामान्य पूल से बिना किसी प्रतिस्थापन के बारी-बारी से ड्रॉइंग लेते हैं, जब तक कि वे कुल>=100 तक नहीं पहुंच जाते।

तो मान लीजिए कि एक पूर्णांक maxChoosableInteger और एक अन्य पूर्णांक वांछित कुल दिया गया है, यह निर्धारित करें कि स्थानांतरित करने वाला पहला खिलाड़ी जीत को मजबूर कर सकता है, यह मानते हुए कि दोनों खिलाड़ी बेहतर तरीके से खेलते हैं।

हम हमेशा मान सकते हैं कि maxChoosableInteger 20 के मान से बड़ा नहीं होगा और वांछित कुल 300 से बड़ा नहीं होगा। इसलिए यदि इनपुट maxChooseableInteger =20 है, और वांछित कुल 11 है, तो परिणाम झूठा होगा। कोई फर्क नहीं पड़ता कि पहला खिलाड़ी चुनता है, पहला खिलाड़ी हार जाएगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• dp आकार 2^21

  called नामक एक सरणी बनाएं

• हल करने के तरीके को परिभाषित करें (), इसमें n, s, और मास्क लगेगा।

• अगर s <=0, तो झूठी वापसी

• अगर dp[mask] -1 नहीं है, तो dp[mask]

  return लौटाएं

• सेट रिट :=असत्य

• I के लिए 1 से n की सीमा में

  • अगर (मास्क I बिट्स को दाईं ओर शिफ्ट करना) विषम है, तो

    • ret :=ret OR (समाधान का व्युत्क्रम(n, s – i, mask XOR 2^i))

• डीपी [मुखौटा]:=सेवानिवृत्त

• वापसी रिट

• मुख्य विधि से, निम्न कार्य करें

• यदि वांछित हैकुल <=0, तो सत्य लौटें

• I के लिए 0 से 2^21 की सीमा में

  • डीपी [i] :=-1

• अगर वांछितकुल> (पहले n संख्याओं का योग), फिर झूठी वापसी करें

• वापसी हल (एन, वांछित कुल, 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