Задание №21
ЕГЭ-2023. Задание 21
Тема: Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию. Время выполнения 11 минут.
Решение задания № 21 ЕГЭ-2023. Демо.
Условие задачи:
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.
я.п. Python:
def F(x,p):
if x >= 129 and (p==5 or p==3): return True
if x < 129 and p==5: return False
if x>=129: return False
if p%2 == 1:
return F(x+1,p+1) and F(x*2, p+1)
else:
return F(x+1,p+1) or F(x*2, p+1)
def FF(x,p):
if x >= 129 and p==3: return True
if x < 129 and p==3: return False
if x >= 129: return False
if p%2==1:
return FF(x+1,p+1) and FF(x*2, p+1)
else:
return FF(x+1,p+1) or FF(x*2, p+1)
for s in range(1, 129):
if F(s, 1):
print(s)
print()
for s in range(1,129):
if FF(s,1):
print(s)
я.п. C/C++:
#include <bits/stdc++.h>
using namespace std;
bool f(int x,int p)
{
if(x>=129&&(p==3||p==5))
return true;
if(x<129&&p==5)
return false;
if(x>=129)
return false;
if(p%2==1)
return f(x+1,p+1)&&f(x*2,p+1);
else
return f(x+1,p+1)||f(x*2,p+1);
}
bool ff(int x,int p)
{
if(x>=129&&p==3)
return true;
if(x<129&&p==3)
return false;
if(x>=129)
return false;
if(p%2==1)
return ff(x+1,p+1)&&ff(x*2,p+1);
else
return ff(x+1,p+1)||ff(x*2,p+1);
}
int main()
{
int s;
for(s=1;s<129;++s)
if(f(s,1))
cout<<s<<' ';
cout<<'\n';
for(s=1;s<129;++s)
if(ff(s,1))
cout<<s<<' ';
return 0;
}
я.п. PascalABC.net:
function f(x,p: integer):boolean;
begin
if (x>=129) and ((p=3) or (p=5)) then begin f:=true;exit end;
if (x<129) and (p=5) then begin f:= false;exit end;
if (x>=129) then begin f:= false;exit end;
if p mod 2 = 1 then
f:=f(x+1,p+1) and f(x*2,p+1)
else
f:=f(x+1,p+1) or f(x*2,p+1);
end;
function f1(x,p: integer):boolean;
begin
if (x>=129) and (p=3) then begin f1:=true;exit end;
if (x<129) and (p=3) then begin f1:= false;exit end;
if (x>=129) then begin f1:= false;exit end;
if p mod 2 = 1 then
f1:=f1(x+1,p+1) and f1(x*2,p+1)
else
f1:=f1(x+1,p+1) or f1(x*2,p+1);
end;
begin
for var s:=1 to 129 do
if f(s,1) then
println(s);
println();
for var s:=1 to 129 do
if f1(s,1) then
println(s);
end.
Ответ: 62
Решения задания № 21 ЕГЭ прошлых лет
Решение.
В предыдущем разборе мы определились с минимальным число камней во второй куче, когда еще возможен выигрыш Пети первым ходом. Следовательно, для выигрыша Вани первым или вторым ходом рассмотрим ситуацию, когда во второй куче будет 30 камней. Решение можно представить как в таблице, так и деревом. Покажем решение данной задачи через построение дерева.
Так как мы показываем выигрышную стратегию Вани, следовательно, при построении дерева будем отображать все ходы Пети и только выигрышные ходы Вани. Наше построение - это только обоснование найденного решения. Советую всегда проверять найденные решения.
Ситуация: (14, 30) - первый ход Пети, на дереве не отражена. Дополните дерево самостоятельным достроением. Вписывается ли данная ситуация в описанную? Ведь, как видно из дерева, у Пети есть только максимальное количество камней - 70, которых не хватит, чтобы победить.
Построенное дерево неполно. Не обозначены действия. Но и так видно, что в данном случае выигрывает Ваня.
Ответ на задачу: 30