Amal và Bimal chơi với mảng height. Mỗi lượt chọn tháp độ cao X, giảm xuống Y (1 ≤ Y < X, Y chia hết X). Người không có nước đi thua. Amal đi trước. Tìm người thắng.
Ví dụ: height=[3,1,2] → Bimal thắng.
Giải thuật
- Với mỗi tháp, tính số lượng ước nguyên tố (có tính lặp) → b[i].
- XOR tất cả b[i]. Nếu != 0 → Amal thắng, ngược lại Bimal thắng.
Ví dụ mã Python
def util(a, n):
ans = 0
for i in range(n):
ans ^= a[i]
return ans
def solve(height):
n = len(height)
b = [0] * n
for i in range(n):
if height[i] == 1:
b[i] = 0
else:
val = height[i]
cnt = 0
j = 2
root = int(val**0.5)
while val != 1 and j <= root:
if val % j == 0:
while val % j == 0:
cnt += 1
val //= j
j += 1
if val != 1:
cnt += 1
b[i] = cnt
ans = util(b, n)
return "Amal" if ans != 0 else "Bimal"
height = [3, 1, 2]
print(solve(height)) # Output: Bimal
Đầu vào
[3,1,2]
Đầu ra
Bimal