পাইথনে একটি সেট উপাদান অপসারণ গেমের বিজয়ী খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে প্রথম n প্রাকৃতিক সংখ্যার একটি সেট আছে {1..n}। অমল আর বিমল একটা খেলা খেলছে। খেলার নিয়ম নিচের মত

অমল সবসময় প্রথম খেলে
প্রতিটি পদক্ষেপের সময়, বর্তমান খেলোয়াড় সেট থেকে একটি মৌলিক সংখ্যা p নির্বাচন করে। প্লেয়ার তারপর সেট থেকে p এবং এর সমস্ত গুণকগুলি সরিয়ে দেয়।
যার কোন চাল নেই সে গেমটি হারাবে যদি আমাদের n থাকে তবে আমাদের বিজয়ীর নাম খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুটটি n =5 এর মত হয়, তাহলে আউটপুটটি হবে Amal, কারণ প্রাথমিক সেটটি হল {1,2,3,4,5}। এখন চলুন অমল একটি সংখ্যা p =2 নির্বাচন করে, এবং সেট থেকে 2, 4 সরিয়ে দেয়, সুতরাং বর্তমান সেটটি হল {1,3,5}, দুটি প্রাইম বাকি আছে, তাই বিমল তাদের যেকোনো একটি নির্বাচন করতে পারে কিন্তু কোনো অবশিষ্ট উপাদান নেই অপসারণ করতে এবং অবশেষে অমল আরেকটি প্রাইমকে সরিয়ে দেয় এবং গেমটি জিতে নেয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

primes :=100000 আকারের একটি অ্যারে, প্রাথমিকভাবে সবগুলি 0
চালনী :=100000 আকারের একটি অ্যারে, প্রাথমিকভাবে সবগুলি 0
আমি 2 থেকে 99999 রেঞ্জের জন্য, কর
- যদি চালনী[i] 0 এর মত হয়, তাহলে
  - primes[i] :=primes[i-1]+1
  - i থেকে 100000 রেঞ্জের j এর জন্য, i দ্বারা প্রতিটি ধাপে আপডেট করুন, করুন
    - চালনি[j] :=i
- অন্যথায়,
  - primes[i] :=primes[i-1]
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
প্রাথমিক [n] বিজোড় হলে "বিমল" ফেরত দিন অন্যথায় "আমল"

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
   if sieve[i] == 0:
      primes[i] = primes[i-1]+1

      for j in range(i, 100001, i):
         sieve[j] = i
   else:
      primes[i] = primes[i-1]

def solve(n):
   return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))

ইনপুট

আউটপুট

Amal