TLE-oj Cup Round 12 - Trò chơi Nim chuẩn

Xem PDF

Nộp bài

Điểm: 1800 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M
Input: NIMGAME.inp
Output: NIMGAME.out

Tác giả:
Dạng bài

huyhau6a2khanhphucscratch rủ nhau chơi một trò chơi. huyhau6a2 mang đến 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:

Phát biểu trò chơi

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)

khanhphucscratch đã chọn ra một số nguyên dương k. huyhau6a2 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à khanhphucscratch sẽ là người được bốc sỏi trước ở trò chơi này. Bạn hãy giúp huyhau6a2 bằng cách chỉ ra một cách chia sỏi sao cho huyhau6a2 luôn thắng cho dù khanhphucscratch có đi như thế nào.

Input, 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 huyhau6a2 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ì huyhau6a2 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

Không có bình luận nào.