Editorial for Bedao Mini Contest 13 - APPLE


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.

Author: bedao

Gọi ~G(a, b)~ là trò chơi có hai hàng táo là ~a~ và ~b~. Nếu người đi trước thắng thì ta gọi ~G(a, b)~ là trạng thái thắng, thua thì gọi là trạng thái thua. Đáp án với mỗi lần chơi là copium nếu ~G(n, m)~ là trạng thái thắng, illya nếu là trạng thái thua.

Do thứ tự của hai hàng táo không quan trọng nên không mất tính tổng quát, ta giả sử ~a \ge b~. Nếu ~b = 0~ thì theo đề bài, ta biết được luôn ~G(a, b)~ là trạng thái thua. Xét ~b > 0~, gọi ~c = a \mod b~, ta để ý ~0 \le c < b \le a~. Ta có nhận xét sau:

Khi hai hàng táo có lần lượt ~a~ và ~b~ quả, thì ta chắc chắn rằng trong lúc chơi, sẽ tồn tại một thời điểm mà một hàng táo có ~b~ quả và hàng còn lại có ~c~ quả.

Điều này hiển nhiên đúng vì ~b~ là hàng có ít táo hơn ~a~, nên người chơi sẽ phải lấy táo trong hàng ~a~ cho đến khi ~a < b~. Do số táo được lấy đi trong mỗi lượt đó phải chia hết cho ~b~, nên số táo cuối cùng của hàng ~a~ sẽ chính bằng ~c = a \mod b~.

Vậy ta đã biến trò chơi ~G(a, b)~ thành một trò chơi nhỏ hơn ~G(b, c)~. Ta có thể dùng đệ quy để tính ~G(b, c)~, vậy chỉ còn việc tìm xem ~G(a, b)~ là trạng thái thắng hay thua dựa trên trạng thái của ~G(b, c)~.

Nếu ~G(b, c)~ là trạng thái thua, thì người đi trước chỉ cần lấy ~a - c~ quả táo (lưu ý ~a - c~ chia hết cho ~b~), khi đó ~G(a, b)~ sẽ biến thành ~G(b, c)~ nhưng ngưới đi trước lại là người còn lại. Do ~G(b, c)~ là trạng thái thua nên người còn lại chắc chắn thua, vậy người đi trước luôn luôn thắng và ~G(a, b)~ là trạng thái thắng.

Nếu ~G(b, c)~ là trạng thái thắng và ~a = b + c~, thì người đi trước chỉ có một nước đi hợp lệ là lấy ~b~ quả táo từ hàng ~a~, khi đó ~G(a, b)~ sẽ biến thành ~G(b, c)~ nhưng ngưới đi trước lại là người còn lại. Do ~G(b, c)~ là trạng thái thắng nên người còn lại chắc chắn thắng, vậy người đi trước luôn luôn thua và ~G(a, b)~ là trạng thái thua.

Nếu ~G(b, c)~ là trạng thái thua, thì người đi trước chỉ cần lấy ~a - c - b~ quả táo (lưu ý ~a - c - b~ chia hết cho ~b~), khi đó ~G(a, b)~ sẽ biến thành ~G(b + c, b)~ nhưng ngưới đi trước lại là người còn lại. Do ~G(b + c, c)~ là trạng thái thua (đây chính là trường hợp ở ngay trên) nên người còn lại chắc chắn thua, vậy người đi trước luôn luôn thắng và ~G(a, b)~ là trạng thái thắng.

Hiểu thêm về lý thuyết trò chơi tại đây


Comments

Please read the guidelines before commenting.


There are no comments at the moment.