Задача 6.
На линейке из m клеток в разных концах стоят две фишки, которые ходят по очереди. Каждая из фишек может ходить влево или вправо не более чем на К клеток (m<=80;К<=m-2). При этом нельзя перешагивать через фишку и нельзя оставаться на месте. Фишка проигрывает, если она не может сделать ход. Написать программу, реализующую выигрышную стратегию для одной из фишек. При этом разрешается передача хода в самом начале игры. Предусмотреть контроль входных данных.
|
Решение задачи 6.
Предположим, что левая фишка (будем называть ее Ф1) можем ходить только вправо, а правая фишка Ф2 - только влево, и ход передавать нельзя. Решение задачи в первоначальной постановке сводится к решению задачи при налагаемых выше ограничениях.
Пусть первый ход делает Ф1. Ф1 выигрывает, если количество клеток между фишками d(Ф1,Ф2) (вначале оно равно m-2) не делится нацело на k+1. Действительно, пусть Ф1 делает такой ход, что d(Ф1,Ф2) кратно k+1. Какой бы ход не сделала Ф2 (например, на L клеток влево), Ф1 следующим ходом смещается на k+1-L клеток вправо, и, таким образом, после хода Ф1 расстояние d(Ф1,Ф2) снова кратно k+1. А так как 0 также делится на k+1 нацело, то наступит момент, когда d(Ф1,Ф2)=0 и предыдущий ход был ходом Ф1, т.е. Ф2 проиграла. Если (m-2) mod (k+1)=0, то Ф1 при наилучших ходах Ф2 проигрывает.
Если разрешить фишкам ходить как влево, так и вправо, то всегда выигрывает та фишка, после хода которой d(Ф1,Ф2) кратно k+1.
|
