Python에서 돌 게임의 승자를 찾는 프로그램

<시간/>

Amal과 Bimal이 게임을 하고 있고 Amal의 차례가 먼저라고 가정합니다. 게임은 아래와 같습니다 -

한 더미에 n개의 돌이 있습니다. 각 플레이어는 더미에서 돌을 가져와 해당 돌의 위치에 따라 점수를 받을 수 있습니다. Amal과 Bimal은 돌의 가치를 다르게 평가할 수 있습니다.

길이가 같은 두 개의 배열 A_Values와 B_Values가 있습니다. 각 A_Values[i] 및 B_Values[i]는 Amal과 Bimal이 각각 i번째 돌을 평가하는 방법을 나타냅니다. 여기에서 점수가 최대인 사람은 모든 돌을 제거한 후 승자가 됩니다. 동점인 경우 게임은 무승부로 이어집니다. 두 플레이어 모두 최적의 상태로 플레이합니다. 둘 다 상대방의 가치를 알고 있습니다. 따라서 Amal이 이기면 1을 반환하고 Bimal이 이기면 -1을 반환합니다. 그리고 무승부 경기의 경우 0을 반환합니다.

따라서 입력이 A_Values =[2,4] B_Values =[3,5]와 같으면 Amal이 포인트 4로 두 번째 스톤을 선택하므로 출력은 1이 됩니다. 3, 하지만 Amal이 더 높은 점수를 가지고 있으므로 그가 이깁니다.

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

n :=A_Values의 크기
combinedValues :=새 목록
0에서 n 사이의 i에 대해
- tmpV :=A_Values[i] + B_Values[i]
- 끝에 결합된 값에 쌍(temV, i) 삽입
combinedValues 목록을 역순으로 정렬
점수_a :=0, 점수_b :=0
0 ~ n - 1 범위의 i에 대해
- curV :=CombinedValues[i]
- i mod 2가 0과 같으면
  - score_a :=score_a + A_Values[curV[1]]
- 그렇지 않으면
  - score_b :=score_b + B_Values[curV[1]]
score_a> score_b이면
- 1을 반환
그렇지 않으면 score_a가 score_b와 같을 때
- 0을 반환
그렇지 않으면
- 반환 -1

예시

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

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

입력

[2,4], [3,5]