Tìm người chiến thắng bằng cách thêm sự khác biệt theo từng cặp của các phần tử trong mảng cho đến khi Có thể bằng Python

Giả sử chúng ta có một mảng A gồm các số nguyên dương, các phần tử là duy nhất, lúc này, hai người chơi P và Q đang chơi một trò chơi. Ở mỗi lần di chuyển, một người chơi bất kỳ chọn hai số a và b từ mảng và nếu | a - b | không có trong mảng sau đó người chơi thêm số này vào mảng. Khi một người chơi không thể thực hiện nước đi sẽ mất trò chơi. Chúng ta phải tìm ra người chiến thắng trong trò chơi nếu người chơi P luôn bắt đầu trò chơi.

Vì vậy, nếu đầu vào là A =[8,9,10], thì đầu ra sẽ là P.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của arr

• g:=arr [0], max_val:=arr [0]

• đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện

  • g:=gcd (g, arr [i])

  • max_val:=tối đa của max_val, arr [i]

• tổng:=(max_val / g) - n

• nếu tổng là số lẻ thì

  • trả về 'P'

• trả về 'Q'

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[8,9,10]

Đầu ra

P