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

Разбор варианта Статграда от 24 октября 2024 года. Часть 3 (24.25)

Разбор варианта Статграда от 24 октябоя 2024 года. Часть 3 (24, 25)

задание 24	Задание 25

Задание 24 (ссылка на задание)

Текстовый файл состоит из цифр от 1 до 6, знаков операций «–» и «*» (вычитание и умножение) и заглавных латинских букв A, B, C, D.
Определите максимальное количество символов в непрерывной последовательности символов, состоящей из буквы A, за которой следует корректное арифметическое выражение с целыми неотрицательными числами, записанными в десятичной системе счисления.

Данное задание нельзя считать очень сложным (задания основной волны 2024 года было сложнее). Это задание надо рассматривать как подготовительное.

Путь к решению виден сразу

считать строку целиком
создать список "сплитуя" по 'A'
выделить из каждого элемента списка "требуемое" начало
вывести лучший результат

Возможные подводные камни

можно забыть, что символ A входит в ответ - ответ будет на 1 меньше требуемого
вместо поиска начального фрагмента проверять всю строку - будет получен возможный ответ и поймать ошибку будет сложно

Предположим, что

Попробуем реализовать программу по этапам
Быстро написали код и получили правдоподобный ответ.

Вначале организовать считывание, "сплитование" и подпрограмму

# код подпрограммы f24 убран
# подпрограмма содержит логическую ошибку
  
f = open('24_24-10.txt') # открытие файла 
sss = f.read().split('A') # получение списка подстрок
ans ='A' # инициализация ответа, и чтобы не забыть про начальное А 
for ss in sss : # пробег по подстрокам
  if len(ss) < len(ans) : # более лучшего ответа не будет
    continue 
  new = 'A' + f24(ss) # получение кандидата в ответ
  if len(new) > len(ans) : # получен новый ответ
    ans = new # фиксфция ответа
    print (ans,'=',sep='') # отладочный вывод с проверкой на "лишние" символы 
print(len(ans)) #вывод ответа

Избежать подобную ошибку можно, если

сделать запуск на ограниченном объёме
организовать отладочную печать

В следующем коде можно менять значения в строке 7, "двигать" оператор print в зону if и смотреть результаты

# код подпрограммы f24 убран
# подпрограмма содержит логическую ошибку
  
f = open('24_24-10.txt') # открытие файла 
sss = f.read().split('A') # получение списка подстрок
ans ='A' # инициализация ответа, и чтобы не забыть про начальное А 
for ss in sss[:10] : # пробег по подстрокам
  if len(ss) < len(ans) : # более лучшего ответа не будет
    continue 
  new = 'A' + f24(ss) # получение кандидата в ответ
  if len(new) > len(ans) : # получен новый ответ
    ans = new # фиксфция ответа
  print (ss,new,sep='\n') # отладочный вывод с проверкой на "лишние" символы 
print(len(ans)) #вывод ответа

Правильный алгоритм для подпрограммы f24(ss) может оприарться на поиск начальной подстроки, в которой

нет символо "BCD" и комбинаций "--", "-*", "*-", "**"
первый и последний символы не '-', '*'

Такую подпрограмму можно реализовать различными способами.
Предложим подход с продвижением указателя до встречи с запретом. Условие запрета на последний символ проверим отдельно

def f24(ss) :
  if ss[0] in 'BCD-*' : # проверка 1-го символа строки 
    return '' 
  j = 0 # инициализация указателя
  while j < len(ss)-1 : # надо проверять следующий, поэтому len(ss) -1
    if (ss[j+1]  in 'BCD') == True : # Stop по правилу 'BCD' / можно not (ss[j+1] in '123456*-') 
      break
    if (ss[j] in '-*') and (ss[j+1] in '*-') : # Stop по правилу "знаков операций"  
      break
    j += 1 # увеличение подстроки
  if ss[j] in '*-' : return ss[:j] # обработка последнего     
  return ss[:j+1]
  
f = open('24_24-10.txt') # открытие файла 
sss = f.read().split('A') # получение списка подстрок
ans ='A' # инициализация ответа, и чтобы не забыть про начальное А 
for ss in sss[:10] : # пробег по подстрокам
  if len(ss) < len(ans) : # более лучшего ответа не будет
    continue 
  new = 'A' + f24(ss) # получение кандидата в ответ
  if len(new) > len(ans) : # получен новый ответ
    ans = new # фиксфция ответа
  print (ss,new,sep='\n') # отладочный вывод с проверкой на "лишние" символы 
print(len(ans)) #вывод ответа

Финальная версия (как на экзамене)

def f24(ss) :
  if ss[0] in 'BCD-*' :  return '' 
  j = 0 
  while j < len(ss)-1 : 
    if (ss[j+1]  in 'BCD'): break
    if (ss[j] in '-*') and (ss[j+1] in '*-') : break
    j += 1 
  if ss[j] in '*-' : return ss[:j]      
  return ss[:j+1]
  
f = open('24_24-10.txt')  
sss = f.read().split('A') 
ans ='A'  
for ss in sss : 
  if len(ss) < len(ans) :  continue 
  new = 'A' + f24(ss) 
  if len(new) > len(ans) : 
    ans = new 
    print (ss[:len(new)],new,sep='\n')  
print(len(ans))

Задание 25 (ссылка на задание)

Пусть M (N) – сумма 2 наибольших различных натуральных делителей натурального числа N, не считая самого числа и единицы.
Если у числа N меньше 2 таких делителей, то M (N) считается равным 0.

Найдите все такие числа N, что 110 250 000 ≤ N ≤ 110 300 000,
а десятичная запись числа M (N) заканчивается на 1002.

В ответе запишите все найденные числа в порядке возрастания.
Каждое число вводите в новой строке.

Задание довольно "хитрое", поскольку требуется найти ДВА делителя.
Вместо максимальных можно искать минимальные и по ним определять максимальные. Это надо сделать для каждого из заданных 50000 чисел

найдем x - минимальный простой делитель числа (он же мнинимальный); kx - степень его вхождения в разложение числа
найдем y - минимальный делитель числа n//x^kx
разберем возможные случаи
- kx> 1 минимальные делители выбираем из набора (x,x²,y)
- kx == 1 минимальные делители (x,y)

Для понимания, зачем это нужно, можно взять число 100 - минимальные делители 2 и 2² , а простые 2, 5
Код программы мог выглядеть так (в коде учитывается, что простые числа и квадраты простых не подходят)

Главное, организовать поиск делителя до "корня"

def f25(n): # программа поиска минимального делителя числа n (универсальная)
  if n % 2 == 0 : return 2
  if n < 9 : return n
  d = 3
  while d * d < n :
    if n % d == 0 : return d
    d+=2
  if n % d == 0 : return d
  return n

for n in range (110250000, 110300001) :
  x = f25(n) # x - минимальный делитель 
  if x == n or x ** 2 == n : # n - простое или квадрат простого
    continue
  D =[x]
  kx =0 
  m=n
  while m % x == 0 :
    m = m // x
    kx +=1
  if kx > 1 : # степень вхождения x > 1, значит x * x
    D.append(x * x) 
  if m > 1 : # значит есть другие простые
    D.append(f25(m)) 
  D.sort() # упорядочили
  a, b = n // D[0], n // D[1] # a, b - наибольшие различные
  if (a + b) % 10000 == 1002 :  # проверка условия на сумму
      print(n, D) # при отладке выводим делители

Вывод списка делителей полезен, он дает понимание сути решения
Практически делается два шага факторизации числа (то есть разложения на множители с учетом степеней)
Приведем решение с использованием факторизации (скорее в ознакомительных целях, чем в практических)

программа fmin_del(n,d) - ищет минимальный делитель не меньший d (это более общая реализации, ускоряющая процесс при факторизации)
программа факторизации f25(n) - получает разложение числа на простые множители и может использоваться для поиска числа делителей и суммы делителей

Программа будет выполняться немного дольше, чем без факторизации

def fmin_del(n, d=2): # программа поиска минимального делителя числа n (универсальная)
  if n % 2 == 0 : return 2
  if n < 9 : return n
  if d < 3 : d = 3  
  while d * d < n :
    if n % d == 0 : return d
    d +=2  
  if n % d == 0 : return d
  return n
def f25(n): # программа факторизации числа  
  A=[] # список делителей
  d=2
  while n > 1 :
    x = fmin_del(n, d)
    k=0 # степень вхождения
    while n % x == 0 : # проверка делимости
      k += 1
      n = n // x
    A.append((x,k)) # фиксация
    d = x
  return A    
L, R = 110250000, 110300001 # интервал проверки
#print(f25(L+1))
for n in range (L, R) :
  F = f25(n) # X - факторизация числа 
  if F[0][0] == n : # n - простое 
    continue
  if (len(F) == 1) and  (F[0][1] == 2) : # n - квадрат простого 
    continue
  x, kx = F[0]
  if kx == 1 : D =[x] # в список делителей заносим минимальный
  else : D =[x,x**2] # в список делителей заносим минимальный и его квадрат
  if len(F) > 1 : # в список делителей добавляем второй простойт
    D.append(F[1][0])
  D.sort() # упорядочили список делителей
  a, b = n // D[0], n // D[1] # a, b - наибольшие различные
  if (a + b) % 10000 == 1002 :  # проверка условия на сумму
      print(n, F) # при отладке выводим делители

Прикрепленные файлы
24_24-10.txt

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

Печать