Python에서 집합 요소 제거 게임의 승자를 찾는 프로그램

<시간/>

처음 n개의 자연수 {1..n}의 집합이 있다고 가정합니다. Amal과 Bimal이 게임을 하고 있습니다. 게임 규칙은 다음과 같습니다.

Amal은 항상 먼저 플레이합니다.
각 이동 중에 현재 플레이어는 세트에서 소수 p를 선택합니다. 그런 다음 플레이어는 세트에서 p와 모든 배수를 제거합니다.
움직임이 없는 사람은 게임에서 지게 됩니다. n이 있으면 승자 이름을 찾아야 합니다.

따라서 입력이 n =5와 같으면 초기 세트가 {1,2,3,4,5}이므로 출력은 Amal이 됩니다. 이제 Amal이 숫자 p =2를 선택하고 집합에서 2, 4를 제거합니다. 따라서 현재 집합은 {1,3,5}이고 두 개의 소수가 남아 있으므로 Bimal은 그 중 하나를 선택할 수 있지만 나머지 요소는 없습니다. 제거하고 마침내 Amal이 다른 소수를 제거하고 게임에서 승리합니다.

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

primes :=크기가 100000인 배열, 처음에는 모두 0입니다.
sieve :=크기가 100000인 배열, 처음에는 모두 0입니다.
2에서 99999 사이의 i에 대해
- 체[i]가 0과 같으면
  - 소수[i] :=소수[i-1]+1
  - i ~ 100000 범위의 j에 대해 i, do
    - 체[j] :=나
- 그렇지 않으면
  - 소수[i] :=소수[i-1]
메인 방법에서 다음을 수행하십시오 -
prime[n]이 홀수이면 "Bimal"을 반환하고 그렇지 않으면 "Amal"을 반환합니다.

예시

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

primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
   if sieve[i] == 0:
      primes[i] = primes[i-1]+1

      for j in range(i, 100001, i):
         sieve[j] = i
   else:
      primes[i] = primes[i-1]

def solve(n):
   return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))

입력

출력

Amal