โปรแกรมหาผู้ชนะเกมลดฝีพายใน Python

สมมติว่าเรามีความสูงของอาร์เรย์ มีหอคอยที่แตกต่างกัน n แห่งที่มีความสูงต่างกัน Amal และ Bimal กำลังเล่นเกม กติกาของเกมมีดังนี้

• อามาลเล่นก่อนเสมอ

• ในระหว่างการเคลื่อนที่แต่ละครั้ง ผู้เล่นปัจจุบันจะเลือกหอคอยสูง X และลดความสูงเป็น Y [1 <=Y

• ใครไม่ขยับจะแพ้เกมนี้

เราต้องหาชื่อผู้ชนะให้เจอ

ดังนั้น หากอินพุตเท่ากับความสูง =[3,1,2] ผลลัพธ์จะเป็น Bimal เนื่องจากความสูงเริ่มต้นคือ {3,1,2} หาก Amal ลดความสูงของหอคอย 2 เป็น 1 Bimal สามารถลด 3 ได้ 1 แต่ Amal ไม่มีการเคลื่อนไหวเพื่อให้ Bimal ชนะ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา a,n
• ตอบ :=0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • ans :=ans XOR a[i]
• คืนสินค้า
• จากวิธีหลักให้ทำดังนี้
• n :=ขนาดความสูง
• b :=อาร์เรย์ขนาด n และเติม 0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • ถ้า height[i] เท่ากับ 1 แล้ว
    • b[i] :=0
  • อย่างอื่น
    • b[i] :=0
    • j :=2
    • root :=พื้นของสแควร์รูทของความสูง[i]
    • ในขณะที่ height[i] ไม่เหมือนกับ 1 และ j<=root ให้ทำ
      • ถ้า height[i] mod j เท่ากับ 0 แล้ว
        • ในขณะที่ height[i] mod j เท่ากับ 0, do
          • b[i] :=b[i] + 1
          • height[i] :=ชั้นของความสูง[i]/j
      • j :=j + 1
    • ถ้า height[i] ไม่เท่ากับ 1 แล้ว
      • b[i] :=b[i] + 1
• ตอบ :=util(b, n)
• ถ้า ans ไม่เหมือนกับ 0 แล้ว
  • ส่งคืน "Amal"
• มิฉะนั้น
  • ส่งคืน "Bimal"

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def util(a,n):
   ans = 0
   for i in range(n):
      ans = ans^a[i]

   return ans

def solve(height):
   n = len(height)
   b = [0 for i in range(n)]

   for i in range(n):
      if(height[i] == 1):
         b[i] = 0
      else:
         b[i] = 0
         j = 2

         root = int(pow(height[i],0.5))
         while(height[i] != 1 and j<=root):
            if(height[i]%j == 0):
               while(height[i]%j == 0):
                  b[i] += 1
                  height[i] = height[i]//j

            j += 1

         if(height[i] != 1):
            b[i] += 1

   ans = util(b, n)

   if(ans != 0):
      return "Amal"
   else:
      return "Bimal"

height = [3,1,2]
print(solve(height))

อินพุต

[3,1,2]

ผลลัพธ์

Bimal