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

สมมติว่า Amal และ Bimal เล่นเกมกัน และ Amal เริ่มก่อน เกมเป็นดังนี้: มี n หินในกอง แต่ละผู้เล่นสามารถเอาหินจากกองและได้คะแนนตามตำแหน่งของหินนั้น Amal และ Bimal อาจให้ค่าหินต่างกัน เรามีอาร์เรย์สองอาร์เรย์ความยาวเท่ากัน A_Values และ B_Values แต่ละ A_Values[i] และ B_Values[i] แสดงว่า Amal และ Bimal ให้ค่าหินลำดับที่ i เท่าไหร่ ใครได้คะแนนมากกว่าจะชนะหลังจากหินหมด ถ้าเสมอ เกมจบเสมอ ทั้งคู่เล่นอย่างเหมาะสม ทั้งคู่รู้ค่าของอีกฝ่าย ถ้า Amal ชนะ return 1 ถ้า Bimal ชนะ return -1 เสมอ return 0

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

วิธีแก้ปัญหา

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