โปรแกรมค้นหาจำนวนการเคลื่อนไหวที่เป็นไปได้เพื่อเริ่มเกมเพื่อชนะโดยผู้เริ่มต้นใน Python

สมมติว่า Amal และ Bimal กำลังเล่นเกม พวกเขามี n ภาชนะที่มีช็อคโกแลตอย่างน้อยหนึ่งอันอยู่ข้างใน คอนเทนเนอร์เหล่านี้มีหมายเลขตั้งแต่ 1 ถึง N โดยที่คอนเทนเนอร์มีจำนวนช็อกโกแลตนับ[i] ตอนนี้เกมเป็นเหมือน ผู้เล่นคนแรกจะเลือกภาชนะและนำช็อคโกแลตหนึ่งอันขึ้นไป จากนั้นผู้เล่นคนที่สองจะเลือกภาชนะที่ไม่ว่างเปล่าและนำช็อคโกแลตหนึ่งอันขึ้นไปจากมัน แบบนี้พวกเขาเล่นสลับกัน เมื่อผู้เล่นคนใดคนหนึ่งไม่มีวิธีหยิบช็อคโกแลตใดๆ เขา/เธอก็จะแพ้ในเกมนั้น หากตาของ Amal เป็นคนแรก เราต้องค้นหาว่า Amal จะทำท่าแรกได้กี่วิธี เพื่อให้เขาชนะเสมอ

ดังนั้น ถ้าอินพุตเหมือน count =[2, 3] ผลลัพธ์จะเป็น 1 เพราะคอนเทนเนอร์เริ่มต้นเหมือน [2, 3] เล่นได้แบบนี้

• อามาลหยิบช็อกโกแลตหนึ่งอันจากภาชนะที่สอง ดังนั้นตอนนี้ [2, 2]
• Bimal หยิบช็อกโกแลตหนึ่งอันจากภาชนะแรก ดังนั้นในปัจจุบัน [1, 2]
• อามาลหยิบช็อกโกแลตหนึ่งอันจากภาชนะที่สอง ดังนั้นตอนนี้ [1, 1]
• Bimal หยิบช็อกโกแลตหนึ่งอันจากภาชนะแรก ดังนั้นตอนนี้ [0, 1]

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

• tmp :=0
• สำหรับแต่ละ c นับ ทำ
  • tmp :=tmp XOR c
• ถ้า tmp เป็นศูนย์ แล้ว
  • คืน 0
• มิฉะนั้น
  • เคลื่อนที่ :=0
  • สำหรับแต่ละ c นับ ทำ
    • ย้าย :=เคลื่อนที่ + (1 เมื่อ (tmp XOR c)
  • การเคลื่อนไหวย้อนกลับ

ตัวอย่าง

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

def solve(count):
   tmp = 0
   for c in count:
      tmp ^= c

   if not tmp:
      return 0
   else:
      moves = 0
      for c in count:
         moves += (tmp^c) < c
      return moves

count = [2, 3]
print(solve(count))

อินพุต

[2, 3]

ผลลัพธ์

1