Editorial for [Problem_of_Week] Trò chơi ăn kẹo


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Ta có ~m = (n-2)/k~ chính là tổng số lượt chơi của 2 người.

(1) Nếu ~m~ chẵn thì hai người sẽ chơi số lượt bằng nhau và B sẽ đi được lượt cuối cùng. Ta thấy khi đó, mỗi người sẽ xoá được ~(n-2)/2 = n/2 - 1~ số. Ta sẽ chỉ ra rằng B luôn có thể ép cho kết quả = 1, dù A đi thế nào. Thật vậy, vì ~m~ chẵn nên ~n~ chẵn, ta chia các số ban đầu thành ~n/2~ cặp các số liên tiếp có dạng ~(1,2),(3,4),...,(n-1,n)~. Vì A chỉ tác động được ~n/2-1~ số nên chắc chắn có 1 cặp số liên tiếp chưa được đụng đến. Vì thế, sau lượt cuối của A thì vẫn còn 1 cặp liên tiếp như thế và B chỉ cần xoá đi ~k~ số kia, giữ lại 2 số đó là được.

(2) Nếu ~m~ lẻ thì A sẽ chơi được nhiều hơn B là 1 lượt, ta kiểm tra được rằng ~n, k~ cùng tính chẵn lẻ: ta sẽ chỉ ra đáp số là ~(n+k)/2 = d~.

  • Chiến lược cho A để ăn được ~d~ kẹo: xoá đi ~k~ số nằm chính giữa, đi từ ~(n-k)/2 \to (n+k)/2 = d~. Đối với các số còn lại, ta thực hiện ghép cặp: ~(1, d+1), (2, d+2), ...~ các số cùng cặp thì cách nhau đúng ~d~ đơn vị. Khi đó, với mỗi lượt của B thì B xoá đi số thuộc cặp nào thì A xoá số thuộc cặp đó, để giữa lại cuối cùng là 2 số cùng cặp nên kq = ~d~.
  • Chiến lược cho B để chặn không cho A ăn quá ~d~ kẹo: tất nhiên A cũng không thể có chiến lược khác để ăn > ~d~ kẹo, vì B ăn được ~(n-2-k)/2~ kẹo nên B có thể ăn tất cả các số nhỏ nhất (nếu A có tham gia ăn các số đó thì càng tốt), nói chung sau các lượt của B thì sẽ mất đi các số ~1,2,...,(n-2-k)/2~ và còn lại từ ~(n-k)/2~ đến ~n~, chênh lệch giữa số đầu và cuối = ~n-(n-k)/2 = (n+k)/2 = d~.

Tóm lại, nếu ~(n-2)/k~ chẵn thì đáp số là 1, ngược lại thì sẽ là ~(n+k)/2~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.