Lý thuyết trò chơi: Định lý Sprague-Grundy và Trò chơi Nim

Mục tiêu kiến thức

• Nắm vững định lý Sprague-Grundy: Mọi trò chơi không thiên vị (Impartial Game) ở trạng thái chuẩn tắc (Normal play convention) đều tương đương với một đống sỏi trong trò chơi Nim với số lượng sỏi bằng giá trị Grundy G(u).
• Hàm Grundy định nghĩa theo hàm mex (Minimum Excluded value):

G(u) = mex{G(v) | u → v}

• Tính chất hợp trò chơi: Giá trị Grundy của hợp các trò chơi con độc lập bằng tổng XOR của các giá trị Grundy thành phần: G = G₁ oplus G₂ oplus … oplus G_K.
• Người đi trước thắng khi và chỉ khi G > 0.

Mô tả bài toán

Có N đống sỏi, đống thứ i ban đầu có S_i viên sỏi. Ở mỗi lượt đi, một người chơi chọn một đống sỏi có ít nhất 1 viên và bốc đi một số viên sỏi. Tuy nhiên, mỗi lần bốc chỉ được phép bốc một số viên sỏi thuộc tập hợp cho phép P = {p₁, p₂, …, p_M} (không được bốc quá số sỏi hiện có trong đống). Người không thể thực hiện nước đi hợp lệ nào nữa là người thua cuộc (Normal play). Hai người chơi Alice và Bob luân phiên đi, Alice đi trước. Cả hai đều chơi tối ưu. Hãy xác định ai là người chiến thắng.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N, S_i ≤ 10⁵.
• Thời gian: 1000ms. Bộ nhớ: 256MB.