Bàn cờ là một giải băng chia ô mã số từ 1 đến N. Hai đấu thủ A và B
đan xen nhau, mỗi người đi một nước, A luôn đi trước. Một quân cờ @ đặt cạnh ô
x. Tại nước đi thứ i phải đẩy quân cờ lên (về phía chỉ số nhỏ) di ô, 1 £ di
£
M và không được lặp lại cách vừa đi của
đấu thủ trước, tức là di ¹ di-1. Đấu thủ nào đến lượt mình không đi nổi
thì thua. Giả thiết là hai đấu thủ đều chơi rất giỏi. Biết N, M, x và A là đấu thủ đi trước. Hãy
cho biết
a) A thắng (ghi 1) hay thua (ghi 0).
b) A thắng hay thua sau bao nhiêu nưới đi?
Giả sử hai đấu thủ đi v nước đi với mức đẩy lần lượt là d1,
d2 ,..., dv thì giả thiết của đề bài cho biết hai mức đẩy
kề nhau là di-1 và di phải khác nhau. Giả sử bàn cờ có N
= 12 ô, quân cờ đặt cạnh ô x = 7, mỗi
nước đi phải di chuyển quân cờ lên 1, 2.., hoặc M = 4 ô và không được lặp lại
nước vừa đi của người trước. Nếu A đi trước thì sẽ có thể thắng sau tối đa 4
nước đi. Chẳng hạn, A đi lên 1 bước d1 = 1 để đến ô 6. B có thể chọn
một trong 3 cách đi ứng với d2 = 2, 3, hoặc 4. để đến ô
4, ô 3 hoặc ô 2. Nếu B chọn d2 = 2 để đến ô 4 thì A di chuyển lên
theo d3 = 3 để đến ô 1 khiến cho B thua. Nếu B chọn d2 =
3 để đến ô 3 thì A di chuyển lên theo d3 = 2 để đến ô 1 khiến cho B
thua. Cuối cùng, nếu B chọn d = 4 để đến
ô 2 thì A di chuyển lên theo d3
= 1 để đến ô 1 khiến cho B thua. các giá trị di theo từng phương án
khi đó là như sau:
Phương án 1: (1, 2,
3).
Phương án 2: (1, 3,
2).
Phương án 3: (1, 4,
1).
Thuật toán
Chúng ta hãy thiết lập sự tương ứng giữa cờ đẩy và cờ bảng
và chỉ ra rằng A thắng cờ đẩy khi và chỉ khi A thắng cờ bảng tương ứng. Cờ đẩy
N ô, giới hạn bước đi M và ô xuất phát x tương ứng với cờ bảng N ô dài, M ô
ngang và vị trí xuất phát (x,y) trong đó y = d1 là nước đi hợp lệ
đầu tiên đến 1 ô thua, x := x-d1.
Có một cách tư duy để có thể dễ dàng tính được (x,y) như
sau. Ta thêm cho cờ bảng một ô giả mang mã số 0 và qui định rằng quân cờ bảng
xuất phát tại ô (x,0) - dòng v, cột 0. Sau đó, trong cuộc chơi với cờ bảng này
không ai được phép di chuyển đến cột 0. Nếu A đi đầu tiên thì chắc chắn sẽ di
chuyển từ ô (x,0) đến một ô mà B chắc thua. Trong thí dụ này, nước đi đầu tiên
của A sẽ là (7,0) à (6,1), tức là chuyển quân cờ từ cột 0 sang cột 1.
Bài cờ đẩy mới xem tưởng như đơn giản nhưng để giải được ta
lại phải xét bài khó hơn nhưng có lời gỉai trong sáng, dẽ hiểu.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét