Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Разное >> Номер 7

[Назад]    [Содержание ]    [Вперед]

  


Номер 7


  Условие: Номер 7


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

  Решение задачи: Номер 7


Решение задачи 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.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017