Amal và Bimal chơi với mảng height (độ cao các tháp). Mỗi lượt chọn tháp độ cao X, phá thành Y tháp độ cao Z (Y*Z=X, Y>1, Z>1). 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
- Tính số Grundy cho mỗi độ cao: g[x] = mex của tập { g[d] nếu x chia hết cho d và d lẻ } ∪ { g[j] nếu x chia hết cho j và j lẻ }.
- XOR tất cả g[height[i]]. Nếu != 0 → Amal thắng, ngược lại Bimal thắng.
Ví dụ mã Python
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])
g = 0
while g in s:
g += 1
result[i] = g
return result
g = util()
def solve(height):
r = 0
for h in height:
r ^= g[h]
return "Amal" if r else "Bimal"
height = [3, 1, 2]
print(solve(height)) # Output: Bimal
Đầu vào
[3,1,2]
Đầu ra
Bimal