Chương trình tìm người thắng cuộc trò chơi đá trong Python

Amal và Bimal chơi game, Amal đi trước. Có n viên đá. Mỗi lượt lấy 1 viên, được điểm theo giá trị viên đó. Amal và Bimal giá trị đá khác nhau (mảng A_Values, B_Values). Ai điểm cao hơn thắng, hòa thì hòa. Cả hai chơi tối ưu, biết giá trị đối phương. Trả về 1 (Amal thắng), -1 (Bimal thắng), 0 (hòa).

Ví dụ: A_Values = [2,4], B_Values = [3,5], đầu ra = 1 (Amal lấy đá 2 được 4 điểm, Bimal chỉ lấy được đá 1 là 3 điểm).

Giải pháp

Sắp xếp đá theo tổng giá trị (A[i]+B[i]) giảm dần, luân phiên chọn:

• n := len(A_Values)
• combinedValues := danh sách (A[i]+B[i], i)
• Sắp xếp combinedValues giảm dần
• score_a := 0, score_b := 0
• Với i từ 0 đến n-1:
  • curV := combinedValues[i]
  • Nếu i % 2 == 0: score_a += A_Values[curV[1]]
  • Ngược lại: score_b += B_Values[curV[1]]
• So sánh score_a và score_b trả về 1, 0, -1

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

[2,4], [3,5]

Đầu ra

1