Chương trình tìm điểm tối đa từ việc lấy đá trong Python

Cho ba đống đá kích thước a, b, c. Mỗi lượt: chọn hai đống khác nhau không rỗng, lấy 1 đá từ mỗi đống, cộng 1 điểm. Trò chơi kết thúc khi còn < 2 đống không rỗng. Tìm điểm tối đa.

Ví dụ: a=4, b=4, c=6 → 7 điểm. Các bước: (4,4,6)→(3,3,6)→(2,3,5)→(1,3,4)→(0,3,3)→(0,2,2)→(0,1,1)→(0,0,0).

Giải thuật (Toán học)

1. minimum = min(a,b,c), maximum = max(a,b,c).
2. left = a + b + c - maximum - minimum (giá trị trung gian).
3. Nếu maximum - left <= minimum:
   • Trả về minimum + left - (1 + minimum - (maximum - left)) // 2.
4. Ngược lại: trả về minimum + min(maximum - minimum, left).

Ví dụ minh họa

def solve(a, b, c):
    minimum = min(a,b,c)
    maximum = max(a,b,c)
    left = a+b+c-maximum-minimum
    if maximum-left <= minimum:
        return minimum + left - (1+minimum-(maximum-left))//2
    return minimum + min(maximum-minimum, left)

a, b, c = 4, 4, 6
print(solve(a, b, c))

Đầu vào

4, 4, 6

Đầu ra

7