배열 높이가 있다고 가정합니다. 높이가 다른 n개의 다른 타워가 있습니다. 아말과 비말이 게임을 하고 있습니다. 게임 규칙은 다음과 같습니다.
-
Amal은 항상 먼저 플레이합니다.
-
각 이동 중에 현재 플레이어는 높이가 X인 타워를 선택하고 각각 높이가 Z인 Y개의 다른 타워로 분해합니다. [Y*Z =X; X 및 Y> 1]
-
움직임이 없는 사람은 게임에서 집니다.
승자의 이름을 찾아야 합니다.
따라서 입력이 height =[3,1,2]와 같으면 초기 높이가 {3,1,2}이므로 출력은 Bimal이 됩니다. Amal이 타워 2의 높이를 높이 1의 타워 두 개로 나누면 새 높이 배열은 {3,1,1,1}이 되고 Bimal은 높이가 3인 타워를 깨고 높이가 1인 타워 세 개를 만들 수 있으므로 Amal은 이동하여 Bimal이 이깁니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- util() 함수를 정의합니다. 제한이 걸리며 초기 제한 값은 10^3+5 입니다.
- result :=크기 제한 및 0으로 채워진 배열
- 범위 2에 있는 i의 경우 - 1을 제한하려면 다음을 수행합니다.
- s :=새로운 세트
- i의 제곱근의 바닥까지 범위 1의 j에 대해 다음을 수행합니다.
- d :=i/j의 몫, r :=i/j의 나머지
- r이 0과 같으면
- j가 홀수이면
- 결과[d])를 s에 삽입
- d가 홀수이면
- 결과[j]를 s에 삽입
- j가 홀수이면
- j :=0
- j가 s에 있는 동안 do
- j :=j + 1
- 결과[i] :=j
- 반환 결과
- g :=util()
- 메인 방법에서 다음을 수행하십시오. -
- r :=0
- 높이 i에 대해 다음을 수행합니다.
- r :=r XOR g[i]
- r이 0이 아니면
- "아말" 반환
- 그렇지 않으면
- "비말" 반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def util(limit=10**3+5):
result = [0] * limit
for i in range(2, limit):
s = set()
for j in range(1, int(i**0.5)+1):
d, r = divmod(i, j)
if r == 0:
if j & 1:
s.add(result[d])
if d & 1:
s.add(result[j])
j = 0
while j in s: j += 1
result[i] = j
return result
g = util()
def solve(height):
r = 0
for i in height:
r ^= g[i]
if r:
return "Amal"
else:
return "Bimal"
height = [3,1,2]
print(solve(height)) 입력
[3,1,2]
출력
Bimal