สมมติว่าเรามีความสูงของอาร์เรย์ มีหอคอยที่แตกต่างกัน n แห่งที่มีความสูงต่างกัน Amal และ Bimal กำลังเล่นเกม กติกาของเกมมีดังนี้
-
อามาลเล่นก่อนเสมอ
-
ในระหว่างการเคลื่อนที่แต่ละครั้ง ผู้เล่นปัจจุบันจะเลือกหอคอยที่มีความสูง X และแยกออกเป็นหอคอย Y ที่มีความสูง Z ต่างกัน [Y*Z =X; X และ Y> 1]
-
ใครไม่ขยับจะแพ้เกมนี้
เราต้องหาชื่อผู้ชนะให้เจอ
ดังนั้น หากอินพุตเท่ากับความสูง =[3,1,2] ผลลัพธ์จะเป็น Bimal เนื่องจากความสูงเริ่มต้นคือ {3,1,2} หาก Amal ทำลายความสูงของหอคอย 2 เป็นสองหอคอยที่มีความสูง 1 อาร์เรย์ความสูงใหม่จะเป็น {3,1,1,1} Bimal สามารถทำลายหอคอยที่มีความสูง 3 และสร้างหอคอยสามแห่งที่มีความสูง 1 ได้ ดังนั้น Amal จึงไม่มี ย้ายดังนั้น Bimal ชนะ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน util() การดำเนินการนี้จะใช้เวลาจำกัด ค่าขีดจำกัดเริ่มต้นคือ 10^3+5
- ผลลัพธ์ :=อาร์เรย์ของขนาดที่จำกัดและเติมด้วย 0
- สำหรับฉันอยู่ในช่วง 2 เพื่อ จำกัด - 1 ทำ
- s :=ชุดใหม่
- สำหรับ j ในช่วง 1 ถึงพื้นของสแควร์รูทของ i ทำ
- d :=ผลหารของ i/j, r :=ส่วนที่เหลือของ i/j
- ถ้า r เท่ากับ 0 แล้ว
- ถ้า j เป็นเลขคี่
- แทรกผลลัพธ์[d]) ลงใน s
- ถ้า d เป็นเลขคี่
- แทรกผลลัพธ์[j] ลงใน s
- ถ้า j เป็นเลขคี่
- j :=0
- ในขณะที่ j มีอยู่ใน s ให้ทำ
- j :=j + 1
- ผลลัพธ์[i] :=j
- ผลตอบแทน
- g :=util()
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- r :=0
- ส่วนสูงแต่ละคน ทำ
- r :=r XOR g[i]
- ถ้า r ไม่ใช่ศูนย์ แล้ว
- ส่งคืน "Amal"
- มิฉะนั้น
- ส่งคืน "Bimal"
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
