Giả sử chúng ta có một chiều cao mảng. Có n tháp khác nhau với chiều cao khác nhau. Amal và Bimal đang chơi một trò chơi. Luật chơi như dưới đây
-
Amal luôn chơi trước
-
Trong mỗi lần di chuyển, người chơi hiện tại chọn một tháp có chiều cao X và chia nhỏ thành Y các tháp khác nhau có chiều cao Z. [Y * Z =X; X và Y> 1]
-
Ai không di chuyển sẽ thua trò chơi
Chúng tôi phải tìm ra tên của người chiến thắng.
Vì vậy, nếu đầu vào giống như height =[3,1,2], thì đầu ra sẽ là Bimal, vì độ cao ban đầu là {3,1,2}. Nếu Amal phá vỡ chiều cao của tháp 2 thành hai tháp có chiều cao 1, thì mảng chiều cao mới sẽ là {3,1,1,1}, Bimal có thể phá tháp có chiều cao 3 và tạo ra ba tháp có chiều cao 1, vì vậy Amal không có di chuyển do đó thắng Bimal.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm use (). Điều này sẽ có giới hạn, giá trị giới hạn ban đầu là 10 ^ 3 + 5
- kết quả:=một mảng giới hạn kích thước và điền bằng 0
- đối với tôi trong phạm vi 2 đến giới hạn - 1, thực hiện
- s:=một tập hợp mới
- đối với j trong phạm vi từ 1 đến tầng của căn bậc hai của i, do
- d:=phần thương của i / j, r:=phần còn lại của i / j
- nếu r giống 0, thì
- nếu j là lẻ, thì
- chèn kết quả [d]) vào s
- nếu d là số lẻ, thì
- chèn kết quả [j] vào s
- nếu j là lẻ, thì
- j:=0
- while j có mặt trong s, do
- j:=j + 1
- kết quả [i]:=j
- trả về kết quả
- g:=use ()
- Từ phương pháp chính, hãy thực hiện như sau -
- r:=0
- đối với mỗi chiều cao của tôi, hãy thực hiện
- r:=r XOR g [i]
- nếu r khác 0, thì
- trả lại "Amal"
- nếu không,
- trả về "Bimal"
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
[3,1,2]
Đầu ra
Bimal