पायथन में जांचें कि अमल स्टोन गेम जीत सकता है या नहीं

मान लीजिए दो खिलाड़ी अमल और बिमल हैं, वे एक खेल खेल रहे हैं, और अमल पहले शुरू करता है। प्रारंभ में, एक ढेर में n अलग-अलग पत्थर हैं। प्रत्येक खिलाड़ी की बारी पर, वह ढेर से कोई भी वर्ग संख्या (शून्येतर) पत्थर हटाने की चाल चलता है। साथ ही, यदि एक खिलाड़ी चाल चलने में असमर्थ है, तो वह खेल हार जाता है। इसलिए यदि हमारे पास n है, तो हमें जांचना है कि अमल खेल जीत सकता है या नहीं।

इसलिए, यदि इनपुट है n = 21, तो आउटपुट True होगा क्योंकि पहले अमल 16 ले सकता है, फिर बिमल 4 लेता है, फिर अमल 1 लेता है और खेल जीतता है।

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

squares := एक नई सूची
square := 1
increase := 3
जब तक square <= n, करें
- square को squares के अंत में डालें
- square := square + increase
- increase := increase + 2
square को squares के अंत में डालें
dp := (n + 1) आकार की एक खाली सूची
dp[0] := False
k को 1 से n तक के लिए, करें
- s := 0
- dp[k] := False
- जब तक squares[s] <= k और dp[k] खाली है, करें
  - यदि dp[k - squares[s]] खाली है, तो
    - dp[k] := True
  - s := s + 1
dp का अंतिम तत्व वापस करें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(n):
    squares = []
    square = 1
    increase = 3
    while square <= n:
        squares.append(square)
        square += increase
        increase += 2
    squares.append(square)
    dp = [None] * (n + 1)
    dp[0] = False
    for k in range(1, n + 1):
        s = 0
        dp[k] = False
        while squares[s] <= k and not dp[k]:
            if not dp[k - squares[s]]:
                dp[k] = True
            s += 1
    return dp[-1]

n = 21
print(solve(n))

इनपुट

आउटपुट

True