Mô Phỏng Trò Chơi Nim Tối Ưu
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 (
FIRSThoặcSECOND) 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$
Community Discussion