กำหนดกริด n แถว m คอลัมน์ Amal และ Bimal เล่นเกม: Amal วาง lotus ที่แถวบน Bimal วาง caterpillar ที่แถวล่าง Amal เริ่มก่อน สลับกันเล่น Amal เคลื่อนที่ไป 8 ทิศทาง Bimal เคลื่อนที่ซ้าย/ขวา/อยู่ที่เดิม Amal ต้องการจับ Bimal เร็วที่สุด Bimal ต้องการอยู่รอดนานที่สุด หากเลือกคอลัมน์สุ่ม หาความคาดหมายของจำนวนการเคลื่อนที่ที่ Amal ชนะ
เช่น n=5, m=7 ผลลัพธ์คือ 4.571428571428571
วิธีแก้ปัญหา
- r := 0
- ลูป l จาก 0 ถึง m-1
- temp := n - 1.0
- ถ้า l >= n: temp := temp + (l - n + 1) * ((l - 1) / m)
- ถ้า l < m - n: temp := temp + (m - n - l) * ((m - l - 2) / m)
- r := r + temp / m
- คืนค่า r
ตัวอย่างโค้ด
def solve(n, m):
r = 0
for l in range(m):
temp = n - 1.0
if l >= n:
temp += (l - n + 1) * ((l - 1) / m)
if l < m - n:
temp += (m - n - l) * ((m - l - 2) / m)
r += temp / m
return r
n = 5
m = 7
print(solve(n, m))Input
5, 7
Output
4.571428571428571
