เกมเพิ่ม |a-b| ลงอาร์เรย์ ผู้ที่ไม่สามารถเพิ่มได้แพ้
กำหนดอาร์เรย์ A ของจำนวนเต็มบวกที่ไม่ซ้ำกัน สองผู้เล่น P และ Q สลับกันเลือกคู่ (a, b) จากอาร์เรย์ หาก |a-b| ไม่อยู่ในอาร์เรย์ ให้เพิ่มเข้าไป ผู้ที่ไม่สามารถหาคู่ใหม่ได้แพ้ P เริ่มก่อน
ตัวอย่าง: A = [8, 9, 10] → P ชนะ
สังเกตสำคัญ
เซตตัวเลขที่เกิดขึ้นจะเป็นทุกจำนวนที่หารด้วย g = gcd(A) ลงตัว และไม่เกิน max(A) จำนวนสมาชิกสุดท้าย = max(A)/g จำนวนการเคลื่อนไหวทั้งหมด = max(A)/g - n หากเป็นคี่ → P ชนะ, คู่ → Q ชนะ
โค้ดตัวอย่าง Python
from math import gcd
def who_is_the_winner(arr):
n = len(arr)
g = arr[0]
max_val = arr[0]
for i in range(1, n):
g = gcd(g, arr[i])
max_val = max(max_val, arr[i])
total = (max_val // g) - n
return 'P' if total % 2 == 1 else 'Q'
print(who_is_the_winner([8, 9, 10])) # P
