Статья Автор: Лебедев Дмитрий

Разбор Статграда от 2025-01-28. Часть 3( 16, 19-20-21, 23)

Задание 16

Функция F(n), где n – неотрицательное целое число, задана следующими соотношениями:
F(n) = 0, если n = 0;
F(n) = F(n//4) + n%4, если n>0 и n%4 < 2;
F(n) = F(n//4) + n%4 – 1, если n%4 ≥ 2.

Найдите минимальное n, для которого F(n) = 27, а F(n + 1) = 16

def f16(n) :
  if n in dp: return dp[n]
  dp[n] = f16(n//4) + n%4
  if n%4 > 1 : dp[n] -= 1
  return dp[n]
dp = {0 : 0, 1:1}
ans = {}
n =0
while 1 :
  n +=1
  f16(n+1)
  if ((dp[n] - dp[n+1]) == 11) :
    if not (dp[n] in ans) :
      sn2 = bin(n)[2:]
      ans[dp[n]] = (n,sn2)
      print(n, dp[n], dp[n+1],sn2,sn2.count('1'))
      if dp[n] >=20 : break
print('ok')      
for a in ans:
  print(a, ans[a])
print('okok')
sn2 ='1'*(27-12)+'0'+'1'*12
n= int(sn2,2)
f16(n); f16(n+1)
print(n, dp[n], dp[n+1],sn2,sn2.count('1'))

from time import process_time as prt
def f16(n) :
  if n in dp: return dp[n]
  dp[n] = f16(n//4) + n%4
  if n%4 > 1 : dp[n] -= 1
  return dp[n]
k1, k2 = map(int,input().split())
dp = {0 : 0, 1:1}
ans = {}
n =0
t0 =prt()
while 1 :
  n +=1
  f16(n+1)
  if ((dp[n] - dp[n+1]) == k2) :
    if not (dp[n] in ans) :
      sn2 = bin(n)[2:]
      ans[dp[n]] = (n,sn2)
      print(n, dp[n], dp[n+1],sn2,sn2.count('1'),prt()-t0)
      if dp[n] >=k1 : break
print('ok')

Задание 23

Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены буквами.
A. Вычти 2
B. Если число кратно 3, Раздели на 3, Иначе Вычти 4
Сколько существует программ, которые преобразуют исходное число 36 в число 4
и при этом траектория вычислений не содержит числа 16?

def f23(n):
  if n in dp : return dp[n]
  if (sf[0] - n)*(sf[1] - n) > 0 : return 0
  dp[n] = f23(n - 2)
  if n %3 == 0 : dp[n] += f23(n // 3)
  else : dp[n] += f23(n-4)
  return dp[n]
start = 4; goal = 20
sf = [start,goal]
dp = { 16: 0, start : 1}
f23(goal)
print(dp[goal],dp)

Задания 19-20-21

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Если количество камней в куче делится на целое k (2 ≤ k ≤ 9), то игрок может убрать из кучи k камней.
Если количество камней в куче не делится ни на одно из указанных чисел, игрок убирает один камень,
после чего выполняет ход по описанному выше правилу

def pi(pos): # получение образа позиции
  A = set()
  while len(A) == 0 :
    for i in range (2,10):
      if pos % i == 0 :
        A.add (pos - i)
    pos -= 1
  return A
def step0(S, sw): # получение W1 - проверка изменилась 
  Y = set()
  for d in S:
    if min(pi(d)) <= sw : # проверяем, что есть ход в выигрышную зону 
      Y.add(d)
  return Y  
def step1(S, X): # получение множеств типа L
  Y = set()
  for d in S:
    if pi(d).issubset(X) : Y.add(d)
  return Y  
def step2(S, X): # получение множеств типа W
  Y = set()
  for d in S:
    if pi(d) & X : Y.add(d)
  return Y  
swin = int(input()) # определяет выигрышную зону
St = set([i for i in range(swin+1,swin*100+1)]) # множество игры
W1 = step0(St, swin) 
St = St - W1
L1 = step1(St,W1)
St = St-L1
print('L1=',sorted(L1))
W2 = step2(St,L1)
St = St-W2
print('W2=',sorted(W2))
L2 = step1(St,W2.union(W1))
print('L2=',sorted(L2))

В функции Step0 изменена проверка позиции на "выигрышность" - проверяется, что в "образе" минимальный элемент "выигрышный" (это логичный, но частный подход, вызван "двунаправленностью" правил ходов в игре)

Задание 19
Укажите минимальное значение S, при котором Петя не может выиграть первым ходом,
но при любом первом ходе Пети Ваня может выиграть своим первым ходом.
ответ:

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

Чтобы оставить комментарий нужна авторизация

Печать