Tìm người thắng cuộc bằng cách thêm hiệu cặp phần tử trong mảng cho đến khi không thể trong Python

Cho mảng A các số nguyên dương khác nhau. Hai người chơi P và Q chơi game: mỗi lượt, người chơi chọn hai số a, b từ mảng, nếu |a - b| chưa có trong mảng thì thêm số này vào. Người không thể thực hiện lượt chơi sẽ thua. Người chơi P luôn đi trước. Ta cần tìm người thắng.

Ví dụ, nếu A = [8, 9, 10], kết quả là P.

Thuật toán giải quyết

• n := len(arr).
• g := arr[0], max_val := arr[0].
• Duyệt i từ 1 đến n-1:
  • g := gcd(g, arr[i]).
  • max_val := max(max_val, arr[i]).
• total := (max_val / g) - n.
• Nếu total lẻ thì trả về 'P', ngược lại trả về 'Q'.

Ví dụ minh họa

from math import gcd

def who_is_the_winner(arr):
    n = len(arr)
    g = arr[0]
    max_val = arr[0]
    for i in range(1, n):
        g = gcd(g, arr[i])
        max_val = max(max_val, arr[i])
    total = (max_val / g) - n
    if total % 2 == 1:
        return 'P'
    return 'Q'

arr = [8, 9, 10]
print(who_is_the_winner(arr))  # P

Đầu vào

[8, 9, 10]

Đầu ra

P