Mô Phỏng Trò Chơi Nim Tối Ưu

Buổi 63 — Interactive & Constructive
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Đây là bài toán mô phỏng trò chơi đối kháng (toàn bộ trạng thái ban đầu được cho trước).

Có $N$ đống sỏi, đống thứ $i$ có $A_i$ viên sỏi. Hai người chơi FIRST và SECOND lần lượt đi nước (FIRST đi trước). Ở mỗi lượt, người chơi hiện tại chọn một đống sỏi khác rỗng và bốc đi ít nhất $1$ viên; người không còn sỏi để bốc là người thua. Cả hai người chơi đều tuân theo chiến lược cố định sau:

  • Nếu tổng XOR của các đống $S = A_1 \oplus A_2 \oplus \dots \oplus A_N \ne 0$ (vị thế thắng), người chơi chọn đống có chỉ số $i$ nhỏ nhất thỏa mãn $(A_i \oplus S) < A_i$ và giảm $A_i$ xuống còn $A_i \oplus S$.
  • Nếu $S = 0$ (vị thế thua), người chơi chọn đống khác rỗng có chỉ số $i$ nhỏ nhất và bốc đi đúng $1$ viên.

Hãy mô phỏng toàn bộ ván đấu cho đến khi hết sỏi và cho biết người thắng cuộc cùng tổng số lượt đi đã diễn ra.

Dữ liệu vào
  • Dòng đầu ghi số nguyên $N$ ($1 \le N \le 100$).
  • Dòng thứ hai ghi $N$ số nguyên $A_1, \dots, A_N$ ($1 \le A_i \le 1000$, tổng $\sum A_i \le 5000$).
Dữ liệu ra
  • Ghi trên một dòng tên người thắng (FIRST hoặc SECOND) và tổng số lượt đi.
Ví dụ
Input Output
2
2 2
SECOND 4
Giới hạn
  • $1 \le N \le 100$
  • $\sum A_i \le 5000$
Draft saved