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

Разбор Статграда 25-4 (от 4 марта 2025)

Краткое условие задачи типа 27

В лаборатории проводится эксперимент, состоящий из множества испытаний. Результат каждого испытания представляется в виде пары чисел. Для визуализации результатов эта пара рассматривается как координаты точки на плоскости, и на чертеже отмечаются точки, соответствующие всем испытаниям. По результатам эксперимента проводится кластеризация полученных результатов: на плоскости выделяется несколько кластеров – кругов радиуса не более 2 единиц так, что каждая точка попадает ровно в один кластер.
Центром кластера считается та из входящих в него точек, для которой минимально максимальное из расстояний до всех остальных точек кластера. При этом расстояние вычисляется по стандартной формуле расстояния между точками на евклидовой плоскости.
В файле записан протокол проведения эксперимента. Каждая строка файла содержит два числа: координаты X и Y точки, соответствующей одному испытанию.
По данному протоколу надо определить минимальное расстояние между центрами двух различных кластеров.
Вам даны два входных файла (A и B), каждый из которых имеет описанную выше структуру. В ответе запишите два числа: сначала минимальное расстояние между центрами кластеров для файла A, затем для файла B.
В качестве значения указывайте целую часть от умножения найденного числового значения на 10000.
Файл А: 27A_25-03.txt
Файл B: 27B_25-03.txt

def dist(xy,pos): # программа вычисления дистанции
    r = (xy[0] - pos[0]) ** 2 + (xy[1] - pos[1]) ** 2
    return r ** 0.5, pos
# блок настройки
fname = '27A_25-03.txt'
dots = [(0,2,0),(0,-2,1),(5,0,2)] # x, y, номер кластера
#fname = '27B_25-03.txt'
#dots = [(-2.5, -2, 0), (-2.5, 2, 1),(1, -3, 2),(1, 3, 3),(3, 0, 4)]
Clasters ={0 : [], 1 : [], 2 : [],3 : [], 4 : []}
ksize = 10000
# Кластеризация
for s in open(fname):
    s= s.replace(',', '.')
    x, y = map(float, s.split())
    r, pos = min(dist((x, y), dot) for dot in dots)
    Clasters[pos[2]].append((x, y))
# Обработка кластеров
Centrs = []
for ind in Clasters:
    if len(Clasters[ind]) == 0 : continue
    centr = None
    for xy in Clasters[ind]:
        r =max(dist(dot,xy)[0] for dot in Clasters[ind])
        if centr == None or centr[0] > r :
            centr = (r,xy)
    Centrs.append(centr[1])
    print(ind, len(Clasters[ind]),centr)
px = sum(xy[0] for xy in Centrs)/len(Centrs)
py = sum(xy[1] for xy in Centrs)/len(Centrs)
print(px*ksize,py*ksize)
# Получение ответа 
ans0 =min([dist(Centrs[i],Centrs[j])[0] for i  in range(len(Centrs)) for j  in range(i+1, len(Centrs))])
ans1 =max([dist(Centrs[i],Centrs[j])[0] for i  in range(len(Centrs)) for j  in range(i+1, len(Centrs))])
print(ans0*ksize, ans1*ksize)      
#Дополнительный блок. Рисование
import matplotlib.pyplot as plt
colors =['red', 'green', 'blue', 'brown', 'black']
for ind in Clasters:
    plt.scatter([xy[0] for xy in Clasters[ind]], [xy[1] for xy in Clasters[ind]], color = colors[ind % 5])
plt.show()
#'''

Условие задания 16

Обозначим через a%b остаток от деления натурального числа a на натуральное число b,
а через a//b – целую часть от деления a на b.
Функция F(n), где n – неотрицательное целое число, задана следующими соотношениями:
F(n) = 0, если n = 0;
F(n) = F(n//10) + n%10, если n>0 и n чётно;
F(n) = F(n//10), если n нечётно.
Сколько существует таких натуральных чисел n, что 10⁷ ≤ n ≤ 6·10⁷ и F(n) = 0?
Задание несложное для "ручного решения", поскольку нетрудно понять какие числа дают F(n) равное 0
А пройдет ли решение программой? ДА.
Вариант А - считает методом "рекурсия в лоб" - большие затраты времени и памяти, но для условия пройдет
Вариант В - считает для всех значений F(n) - просто без затрат памяти, но очень медленно

# Вариант А для k < 6
def f16(n) :
  if n in dp : return dp[n]
  dp[n] = f16(n//10)
  if n % 2 == 0 : dp[n] += n % 10
  return dp[n]
k = int(input())
dp = {0: 0}
ans = sum (1 for i in range(10**k, 6*10**k +1) if f16(i) == 0)
print(ans)

# Вариант B 
def f16(n) :
  r =0
  while n > 0 :
    a = n % 10 
    if a % 2 == 0 : r += a
    n = n // 10
  return r  
k = int(input())
dp = {}
for i in range(10**k, 6*10**k +1) :
  r = f16(i) 
  if r in dp : dp[r] += 1
  else : dp[r] = 1
print(dp[0])

Условие задания КЕГЭ-19.20.21

Задание А(19).
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
Если количество камней в куче делится на целое k , то игрок может добавить в кучу k камней.
Например, если в куче 6 камней, то за один ход можно добавить 1, 2, 3 или 6 камней.
Игра завершается, когда количество камней в куче становится более 91
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу,
в которой будет 92 или более камней.
В начале игры в куче было S камней, S < 92.
Укажите минимальное значение S, при котором Петя не может выиграть первым ходом,
но при любом первом ходе Пети Ваня может выиграть своим первым ходом.

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

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

def pi(pos) : # pi от слова периферия - окружение
  return dpi[pos] 
def fdel(n) :
  a = {1+n, n+n}
  for i in range(2, n) :
    if n % i == 0 : a.add(i+n)
  return a  
  
def step (S, X, t): # поиск результата такта t
  Y = set() # результат работы
  for pos in S : # перебор игровых точек и поиск результата в зависимости от такта работы
    if (t % 2 == 1) and (pi(pos) & X)  or  (t % 2 == 0) and (pi(pos) <= X): Y.add(pos) 
  return Y 
swin = int(input()) # параметры игры
dpi = {}
for i in range(1, swin) : dpi[i] = fdel(i) 

G = set([i for i in range(1, swin)]) # Множство стартовых точек
LW = {1 : set([i for i in range (swin, 2*swin)]), 0 : set()} # словарь исходов L = LW[0], W = LW[1]
print(pi(swin-1))  
t = 0 # инициализация такта
while t < 10: # просмотр 6 тактов работы
  t +=1 # переход к новому такту
  R = step(G, LW[t % 2], t) # получение результата работы
  G = G - R #  уменьшение множества G
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R) # перенос результатов в финальные множества 
  print('R{} = '.format(t),sorted(R),) # вывод результатов

Условие задания КЕГЭ 23
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены буквами.
A. Прибавь 1
B. Умножь на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 36,
и при этом в процессе вычислений на экране ни разу не появляется цифра 2?

def f23 (n) :
  if n in dp : return dp[n]
  if (n- sf[0])*(n - sf[1]) > 0 : return 0
  if '2' in str(n) :
    dp[n] = 0
    return dp[n]
  dp[n] = f23(n + 1) + f23(2 * n)
  return dp[n]
start, goal = list(map(int,input().split()))
sf = [start, goal]
dp = {goal : 1}
f23(start)
print(dp[start])

Прикрепленные файлы
27A_25-03.txt
27B_25-03.txt

Печать