Загрузка...Задание КИМ № 19: Теория игр
Раздел № 163: Задачи с одной кучей камней (ответ - число)
| Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок. Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу из 5, 6 или 12 камней. Если Петя добавил 1 камень и получил кучу из 5 камней, то следующим ходом Ваня может либо добавить 2 камня (и получить 7 камней), либо утроить количество камней в куче (их станет 15). Получить 6 камней Ваня не может, так как для этого нужно добавить 1 камень, а такой ход только что сделал Петя. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 62. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 62 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 61. Ответьте на следующие вопросы: Вопрос 1. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Вопрос 2. Определите, минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. Вопрос 3. Найдите значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. |
Данная задача решена на языке программирования - Python.
После оплаты Вы сможете скачать программный код.
Ниже представлен код для решения задания 19. Чтобы получить код на 20 и 21 задачи, оплатите товар.
def f(x,z,a):
if x>=61 and z == 3:
return True
if x>=61 and z != 3:
return False
if x < 61 and z == 2:
if a==1:
return f(x+2,z+1,2) or f(x*3,z+1,3)
if a==2:
return f(x+1,z+1,1) or f(x*3,z+1,3)
if a==3:
return f(x+1,z+1,1) or f(x+2,z+1,2)
return f(x+1,z+1,1) or f(x+2,z+1,2) or f(x*3,z+1,3)
if x < 61 and z == 1:
if a==1:
return f(x+2,z+1,2) and f(x*3,z+1,3)
if a==2:
return f(x+1,z+1,1) and f(x*3,z+1,3)
if a==3:
return f(x+1,z+1,1) and f(x+2,z+1,2)
return f(x+1,z+1,1) and f(x+2,z+1,2) and f(x*3,z+1,3)
for i in range(1,62):
if f(i,1,0):
print(i)
break
1) 20 2) 7 19 3) 6
сайт Полякова