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

(The Last Inch) КЕГЭ- 12. Модель решения

Разбор задания КЕГЭ-12 из Тренировочного вариант №1

Первое, что "приходит в голову" - это решение перебором по нисходящей модели.
Реализуем его, используя подпрограмму для преобразования
(главное - не забыть добавить 1 в replace !!!)

def f(n): # программа обработки строки - калька с условия
  s = '4' + '7' * n
  while ('444' in s) or ('777' in s) :
    if '777' in s : 
      s = s.replace('777', '4', 1)
    else :
      s = s.replace('444', '7', 1)
  return s
ans, n = 0, 1000 # параметры обработки
while n > 4 : # нисходящая модель перебора
  n -=1 # уменьшение числа
  s = f(n) # получение результата преобразования
  r = sum(int(x) for x in s) # вычисление суммы значений цифр строки
  if r >= ans : # проверка результата (условие >= позволяет увидеть цикличность)
    ans = r # фиксация результата
    print(r, n) # промежуточная печать 
print('Ответ :', ans)   # вывод ответа

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

Разбор задания КЕГЭ-12 из Тренировочного вариант №1

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
  ЕСЛИ нашлось (25)
    ТО заменить (25, 5)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (355)
    ТО заменить (355, 522)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (555)
    ТО заменить (555, 3)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с цифры "2", а затем содержащая n цифр "5" (3 < n < 10 000).
Определите наименьшее значение n, при котором в строке, получившейся в результате выполнения программы, количество цифр «2» равно 10.

Решение перебором по восходящей модели.
Реализуем его, используя подпрограмму для преобразования
(для понимания процесса добавим поиск максимума и промежуточную печать)

def f(n): # программа обработки строки - калька с условия
  s = '2' + '5' * n
  while ('25' in s) or ('355' in s) or ('555' in s) :
    if '25' in s : 
      s = s.replace('25', '5', 1)
    if '355' in s : 
      s = s.replace('355', '522', 1)
    if '555' in s : 
      s = s.replace('555', '3', 1)
  return s
n, flag, ans = 3, True, 0 # параметры обработки
while flag: # восходящая модель перебора
  n += 1 # увеличени числа
  s = f(n) # получение результата преобразования
  r = s.count('2') # подсчет числа цифр 2
  if r> ans :
    ans = r
    print(ans, n, s) # промежуточная печать
  if r == 10 : flag = False
print('Ответ :', n)   # вывод ответа

Разбор задания КЕГЭ-12 из Тренировочного вариант №3 (аналог задания из №1)

Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (11) ИЛИ нашлось (444) ИЛИ нашлось (8888)
  ЕСЛИ нашлось (11)
    ТО заменить (11, 4)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (444)
    ТО заменить (444, 88)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (8888)
    ТО заменить (8888, 1)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход приведённой выше программе поступает строка, начинающаяся с цифры «8», а затем содержащая и n цифр «4» (3 < n < 10 000).
Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.

В этот раз попробуем использовать периодичность итоговых последовательностей и реализуем решение по восходящей модели.

def f(n): # программа обработки строки - калька с условия
  s = '8' + '4' * n
  while ('11' in s) or ('444' in s) or ('8888' in s) :
    if '11' in s : 
      s = s.replace('11', '4', 1)
    if '444' in s : 
      s = s.replace('444', '88', 1)
    if '8888' in s : 
      s = s.replace('8888', '1', 1)
  return s
ans, n, rs = 0, 3, set() # параметры обработки
while n < 1000 : # восходящая модель перебора
  n += 1 # увеличение числа
  s = f(n) # получение результата преобразования
  rs.add(s) # для прикола сохраняем результаты работы
  r = sum(int(x) for x in s) # вычисление суммы значений цифр строки
  if r > ans : # проверка результата (условие >= позволяет увидеть цикличность)
    ans = r # фиксация результата
    print(r, n, len(rs)) # промежуточная печать 
print('Ответ :', ans, 'вариантов строк =', len(rs))   # вывод ответа

Посмотрев результаты работы, можно понять, что период равен 33 и это число совпадает с количеством различных вариантов

Печать