Python에서 가능까지 배열 요소의 Pairwise 차이를 추가하여 승자를 찾습니다.

양의 정수로 구성된 배열 A가 있고 요소가 고유하다고 가정하고 이제 두 명의 플레이어 P와 Q가 게임을 하고 있습니다. 각 이동에서 한 플레이어는 배열에서 두 개의 숫자와 b를 선택하고 |a – b| 플레이어가 이 숫자를 배열에 추가한 후 배열에 없습니다. 플레이어가 이동을 할 수 없으면 게임에서 집니다. 플레이어 P가 항상 게임을 시작한다면 우리는 게임의 승자를 찾아야 합니다.

따라서 입력이 A =[8,9,10]과 같으면 출력은 P가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=arr의 크기
g :=arr[0], max_val :=arr[0]
범위 1에서 n까지의 i에 대해 수행
- g :=gcd(g, arr[i])
- max_val :=max_val의 최대값, arr[i]
총계 :=(max_val / g) - n
합계가 홀수이면
- 반환 'P'
'Q'를 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

[8,9,10]