n viên sỏi và hai người dự định sẽ chơi một trò chơi Nim chuẩn. Trò chơi được phát biểu như sau:
và rủ nhau chơi một trò chơi. mang đếnPhát biểu trò chơi
Có k đống sỏi, và mỗi đống lần lượt có p_1,p_2,…,p_k sỏi, trong đó mỗi số p_i là một số nguyên không âm. Mỗi trạng thái trò chơi tương ứng với mỗi bộ n cho biết số sỏi của từng đống này.
Có hai người chơi thay phiên nhau bỏ sỏi. Người chơi trong lượt hiện tại có thể loại bỏ bao nhiêu sỏi tùy thích, miễn là tất cả các sỏi đều cùng một đống. Hình thức hơn, người chơi sẽ chọn một đống sỏi i và số lượng sỏi s để loại bỏ khỏi đống (0<s≤p_i), sau đó thay p_i bằng p_i−s. Chú ý rằng người chơi không thể bỏ qua lượt của mình mà không bỏ viên sỏi nào cả. Sau đó, đến lượt người chơi kia loại bỏ sỏi, lần lượt như vậy tới khi trò chơi kết thúc.
Trò chơi kết thúc khi không còn sỏi trên bàn chơi. Người chiến thắng là người lấy được viên sỏi cuối cùng. Nói cách khác, người thua cuộc là người đầu tiên không thể lấy sỏi trong lượt của mình.
(Nguồn: VNOI Wiki)
k. buộc phải chia n viên sỏi thành k đống, mỗi đống có ít nhất một viên và sẽ là người được bốc sỏi trước ở trò chơi này. Bạn hãy giúp bằng cách chỉ ra một cách chia sỏi sao cho luôn thắng cho dù có đi như thế nào.
đã chọn ra một số nguyên dươngInput, Output và Subtasks
Input: (NIMGAME.inp
)
- Một dòng duy nhất gồm hai số nguyên dương n, k (1 \le k \le \min(10^6, n), 1 \le n \le 10^{18})
Output: (NIMGAME.out
)
- Dòng đầu tiên in
YES
nếu tồn tại cách sắp xếp cho luôn thắng, vàNO
trong trường hợp ngược lại. - Nếu dòng đầu tiên in
YES
, dòng thứ hai in ra một dãy p bất kỳ thỏa mãn điều kiện.
Subtasks
- Subtask 1 (20\%): n \le 10.
- Subtask 2 (30\%): n \le 100.
- Subtask 3 (20\%): n \le 1000.
- Subtask 4 (30\%): Không có giới hạn gì thêm.
Sample 1
Input (NIMGAME.inp
)
10 9
Output (NIMGAME.out
)
NO
Note
- Cách duy nhất để chia 10 viên sỏi vào 9 đống là có 8 đống 1 viên và 1 đống 2 viên. Với cách chia này thì luôn thua.
Sample 2
Input (NIMGAME.inp
)
10 5
Output (NIMGAME.out
)
YES
1 2 2 2 3
Note
- Không có note.
Bình luận