পাইথনে অমল স্টোন গেম জিতে পারে কিনা চেক করার প্রোগ্রাম

মনে করুন দুজন খেলোয়াড় অমল এবং বিমল একটি গেম খেলছে, এবং অমল প্রথমে শুরু করবে। শুরুতে পিলে nটি ভিন্ন স্টোন আছে। প্রতিটি খেলোয়াড় তার টার্নে যেকোনো স্কোয়ার নম্বর (নন-জিরো) স্টোন পিল থেকে বাদ দিতে পারে। এবং যদি একজন খেলোয়াড় মুভ করতে না পারে, তবে সে হারে যাবে। n দেওয়া থাকলে অমল গেম জিতে পারে কিনা চেক করতে হবে।

যেমন, ইনপুট n = 21 হলে, আউটপুট হবে True কারণ প্রথমে অমল ১৬ নেয়, তারপর বিমল ৪ নেয়, এবং অমল ১ নিয়ে গেম জিতবে।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

• squares := একটি নতুন লিস্ট

• square := 1, increase := 3

• যখন square <= n, तब

  • square কে squares-এ অ্যাপেন্ড করুন

  • square := square + increase

  • increase := increase + 2

• square কে squares-এ অ্যাপেন্ড করুন

• dp := None দিয়ে (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[-1] রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

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))

ইনপুট

21 

আউটপুট

True