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

Про цифры числа Пи

Текстовый файл состоит из 10 млн десятичных цифр дробной части числа \(\pi\)
Найдите длину максимальной подстроки, сумма цифр которой кратна 7 и она не содержит одинаковых цифр подряд.
В ответе укажите количество символов в такой подстроке

Способов решения может быть несколько.

Произвести замены комбинаций "xx" на "x_x" для всех x (0,1,...9)
Сделать сплит по "_" и далее исследовать отрезки
Применить метод "двух указателей": первый на начале последовательности, второй бежит до запретной комбинации
Далее обработка полученного отрезка и "скачок" первого указателя на место второго.
Комбинированный способ, который и будет применен.

Для способа I, обычно используют сортировку по длине отрезков. Вообще это достаточно трудоемко, поэтому можно:

найти максимальную длину
"оставить только длинные" и отсортировать только их

В чем состоит предлагаемая идея:

Найти в последовательности все индексы i : s[i] == s[i-1] (s - исследуемая строка) - это "по существу точки сплитования"
Создать список границ таких отрезков: [(i,j) ... ]
Найди максимум длин этих отрезков и оставить "верхушку" (например те, у которых длина больше 90% от максимума)
Отсортировать и вывести "нужную" статистику/информацию для "визуального отбора"

ЗЫ. Похоже длина кода будет меньше описания :)

s = open('24_pi.txt').read()
a = [0] + [i for i in range(1, len(s)) if s[i]==s[i-1]]
d = max([a[i] - a[i-1] for i in range(1, len(a))])
print(f'{len(s)=:_} {len(a)=:_} max(len)= {d} sr(len)={len(s)/len(a):.3f}') 
pd = d * 9 // 10
r = [(a[i] -a[i-1], a[i-1], a[i])  for i in range(1, len(a)) if a[i] -a[i-1] >pd]
r.sort(reverse = True)
for l, i, j in r :
  print(f'{l=} sum % 7 ={sum([int(x) for x in s[i : j]]) % 7} {s[i: i+5]}...{s[j-5:j]} [{i:_};{j:_}]')

Выполнив код (в котором есть вывод промежуточной информации) получим:

len(s)=10_000_000 len(a)=1_000_192 max(len)= 128 sr(len)=9.998
l=128 sum % 7 =4 29036...46343 [1_749_889;1_750_017]
l=121 sum % 7 =4 26392...63172 [7_270_846;7_270_967]

информацию о двух строках.
Остаток в первой строке равен 4, значит надо убрать "с краев" цифры, сумма которых % 7 == 4.
"Минимально" это можно сделать, убрав слева пару цифр (29, т.к. (2+9)%7 = 4)
Ответ на задани: 126 цифр.

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

Attached files
24_pi.txt

Печать