ЕГЭ-2023. Задание 19

Тема: Умение анализировать алгоритм логической игры. Время выполнения 6 минут.

Разбор задания № 19 ЕГЭ-2023. Демо.

В файле разобран алгоритм решения задачи. Здесь же покажу решение с помощью я.п.

Приведем условие задачи:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 129 или больше камней.

В начальный момент в куче было S камней, 1 ≤ S ≤ 128.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

я.п. Python:

def f(x,p):

            if x>=129 and p==3: return True

            if x<129 and p==3:  return False

            if x>=129 and p<3:

                                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)

for s in range(1,129):

              if f(s,1):

                           print(s)

                           break

я.п. C/C++:

#include <bits/stdc++.h>

using namespace std;

bool f(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!=0)

        return f(x+1,p+1)&&f(x*2,p+1);

     else

        return f(x+1,p+1)||f(x*2,p+1);

}

int main()

{

    for(int s=1;s<129;++s)

        if(f(s,1))

            cout<<s<<' ';

    return 0;

}

я.п. PascalABC.net:

function f(x,p: integer):boolean;

begin

  if (x>=129) and (p=3) then begin f:=true;exit end;

  if (x<129) and (p=3) 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;

begin

  for var s:=1 to 129 do

    if f(s,1) then

      print(s);

end.

Ответ: 64

Решение заданий № 19 ЕГЭ прежних лет