โปรแกรมหาผู้ชนะเกมหินใน Python

สมมติว่า Amal และ Bimal กำลังเล่นเกมและตาของ Amal เป็นอันดับแรก เกมเป็นเหมือนด้านล่าง −

มีก้อนหินอยู่ n กอง ผู้เล่นแต่ละคนสามารถนำหินออกจากกองและรับคะแนนตามตำแหน่งของหินนั้น Amal และ Bimal อาจเห็นคุณค่าของหินในลักษณะที่แตกต่างกัน

เรามีอาร์เรย์สองอาร์เรย์ที่มีความยาวเท่ากัน A_Values ​​และ B_Values A_Values[i] และ B_Values[i] แต่ละอันแสดงถึงวิธีที่ Amal และ Bimal ให้ความสำคัญกับ ith stone ตามลำดับ ที่นี่ซึ่งมีคะแนนสูงสุดเขาจะเป็นผู้ชนะหลังจากนำหินทั้งหมดออกไป หากเสมอกัน เกมจะส่งผลให้เสมอกัน ผู้เล่นทั้งสองจะเล่นได้ดีที่สุด ทั้งคู่รู้คุณค่าของอีกฝ่าย ดังนั้นถ้า Amal ชนะ ให้คืนค่า 1 ถ้า Bimal ชนะ ให้คืนค่า -1 และสำหรับการแข่งขันที่เสมอกัน ให้คืนค่า 0

ดังนั้นหากอินพุตเป็นเหมือน A_Values ​​=[2,4] B_Values ​​=[3,5] ผลลัพธ์จะเป็น 1 เพราะ Amal จะเลือกหินก้อนที่สองที่มีจุดที่ 4 ดังนั้น Bimal มีโอกาสเพียงครั้งเดียวที่จะได้หินก้อนแรกที่มีคะแนน 3 แต่เนื่องจาก Amal มีคะแนนมากกว่า เขาจึงชนะ

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

• n :=ขนาดของ A_Values
• combinedValues ​​:=รายการใหม่
• สำหรับฉันในช่วง 0 ถึง n ให้ทำ
  • tmpV :=A_Values[i] + B_Values[i]
  • ใส่คู่ (temV, i) ลงในค่าที่รวมกันในตอนท้าย
• เรียงลำดับรายการรวมค่าในลำดับย้อนกลับ
• score_a :=0, score_b :=0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • curV :=รวมค่า[i]
  • ถ้าฉัน mod 2 เหมือนกับ 0 แล้ว
    • score_a :=score_a + A_Values[curV[1]]
  • มิฉะนั้น
    • score_b :=score_b + B_Values[curV[1]]
• ถ้า score_a> score_b แล้ว
  • คืน 1
• มิฉะนั้น เมื่อ score_a เหมือนกับ score_b แล้ว
  • คืน 0
• มิฉะนั้น
  • คืน -1

ตัวอย่าง

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

def solve(A_Values, B_Values):
   n = len(A_Values)
   combinedValues = []
   for i in range(n):
      tmpV = A_Values[i] + B_Values[i]
      combinedValues.append([tmpV, i])

   combinedValues.sort(reverse=True)

   score_a, score_b = 0, 0
   for i in range(n):
      curV = combinedValues[i]
      if (i % 2 == 0):
         score_a += A_Values[curV[1]]
      else:
         score_b += B_Values[curV[1]]

   if (score_a > score_b):
      return 1
   elif (score_a == score_b):
      return 0
   else:
      return -1

A_Values = [2,4]
B_Values = [3,5]
print(solve(A_Values, B_Values))

อินพุต

[2,4], [3,5]

ผลลัพธ์

1