Загрузка...(№ 3078) (А. Кабанов) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня, добавить в кучу три камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17, 18 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 29.
Ответьте на следующие вопросы:
Вопрос 1. Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Вопрос 2. Сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Вопрос 3. Найдите два значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.
Задача решена на двух языках программирования - Python и Pascal. Каждая задача решена в отдельной программе.
Ниже можно увидеть код для решения задачи номер 19.
Python
def f(x,q):
if x>=30 and q==3:
return True
if x>=30 and q<3:
return False
if x<30 and q==2:
return f(x+2,q+1) or f(x*2,q+1) or f(x+3,q+1)
if x<30 and q==1:
return f(x+2,q+1) and f(x*2,q+1) and f(x+3,q+1)
for s in range(1,29):
if f(s,1)==True:
print(s)
Pascal
function f(x,q:integer):boolean;
begin
if (x>=30) and(q=3) then result:=true;
if (x>=30) and(q<3) then result:=false;
if (x<30) and(q=2) then result:=f(x+2,q+1) or f(x*2,q+1) or f(x+3,q+1);
if (x<30) and(q=1) then result:=f(x+2,q+1) and f(x*2,q+1)and f(x+3,q+1);
end;
begin;
for var s:=1 to 29 do
if f(s,1)=true then print(s);
end.
19: 13. 20: 4. 21: 8 9
сайт Полякова
