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

Задания и решения

Задание 25.
Пусть M – сумма двух наибольших простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение М считается равным нулю.
Напишите программу, которая перебирает целые числа, бо́льшие 8 004 389 828, в порядке возрастания и ищет среди них такие, у которых значение M больше 70 000, является простым числом и в своём написании содержит последовательность цифр 45 (45 – идущие подряд друг за другом в указанном порядке цифры 4 и 5) ровно один раз.
В ответе запишите для первых 5 найденных чисел соответствующие им значения M.

Анализ,
Задание очень интересное своей формулировкой - не сразу поймешь, за что "цепляться"
М - простое числа, большее 70_000 и содержащее в своей записи число 45 ... но М - сумма двух простых, значит....

одно из этих простых число 2 !!! - далее все просто ...
M = 2 +P (простое) и 2, P наибольшие делители числа N
=> N = 2^k*P^l, где P > 69999 то есть 2*P² > 2*4_900_000_000
но нужные числа явно не больше 9_000_000_000 :}
итак М = 2^k*P, где P - простое

from time import process_time as prt
ts = prt()
def mindel(n):
  if n % 2 == 0 : return 2
  if n < 9 : return n
  for d in range (3, int(n**0.5)+3,2):
    if n % d == 0 : return d
  return n
N = 8_004_389_828
k = 5
while k>0 :
  N +=2
  n = N 
  while n % 2 == 0 : n = n// 2
  if str(n + 2).count('45') != 1 : continue
  if n == mindel(n) :
    k -= 1
    print(n +2, N)
print(f'time = {prt() - ts}')

Значение арифметического выражения 7⁴⁰⁰ + 7¹⁶⁰ – x, где x – целое положительное число, не превышающее 240_000_000, записали в семеричной системе счисления. Определите наибольшее значение x, при котором в семеричной записи числа, являющегося значением данного арифметического выражения, содержится ровно 220 нулей.
В ответе запишите число в десятичной системе счисления.

n = 230_000_000
s = ''
while n > 0 :
  s = str(n%7) + s
  n = n // 7
print(s)  
t = '5455555555'
print(int(t,7)+1)

a = 7**40000
b = 7**20000
x = 100
k = 0
for x in range (2300, 0, -1):
  n = a+b-x
  while n> 0:
    if n%7 == 0 : k+=1
    n = n // 7
  if k == 20000 :
    print(x, k)

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.
.........................................................................
Определите количество процессов, которые начнутся не ранее 12-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

def zap(s):
    i, t, sp = s.split()
    return int(i), int(t), set(map(int, sp.split(';')))


df = [zap(s) for s in open('22.txt')]
z = {0: (0, 0)}

while len(z) <= len(df):
    sz = set(z)
    for i, t, sp in df:
        if i in z:
            continue
        if sp <= sz:
            ts = max([z[p][0] for p in sp])
            z[i] = (t + ts, ts, i)

z.pop(0)
print(sorted(z.values()))
ans = [z[p] for p in z if z[p][1]>=12]
print(ans)

def zap(s):
    i,t,sp = s.split()
    return int(i), int(t), set(map(int, sp.split(';')))

df = [zap(s) for s in open('22.txt')]
z = {0:(0,0)}
     while len(z) <= len(df) :
     sz = set(z)
     for i, t, sp in df :
     if i in z : continue
     if sp <= sz :
     ts = max([z[p][0] for p in sp])
     z[i] = (t+ts, t,i)
z.pop(0)
print([z[p] for p in z if Z[p][1] >= 12])

Задания 23
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 17 в вершину с номером 67.

dist, vs = {}, set()
x, y = '17', '67'

for s in open('23.txt'):
        a, b, d = s.split()
        dist[(a, b)] = float(d)
        vs.add(a)
        vs.add(b)
        
k = 1
while k > 0:
    k = 0
    for b in vs:
        edge = [(a, c) for a in vs for c in vs if (a, b) in dist and (b, c) in dist]
        for a, c in edge:
            d = dist[(a, b)] + dist[(b, c)]
            if (a, c) not in dist or d < dist[(a, c)] :
                dist[(a, c)] = d
                k += 1
                if (x, y) == (a, c):
                    print(f'{dist[(x, y)]=}')
    print(f'{k=}')

Задание 24
Текстовый файл состоит из заглавных букв латинского алфавита – цифр римской системы счисления I, V, X. Определите в прилагаемом файле максимальное количество идущих подряд символов, которые представляют собой корректную римскую запись нечётного десятичного числа. Если найденных последовательностей несколько, выберите ту, для которой абсолютная разность индексов первого символа последовательности и первого символа ближайшего римского числа XXXVIII в файле не менее 9400. Гарантируется, что в файле есть однаединственная искомая последовательность. В ответе укажите индекс первого символа найденной последовательности римских цифр. В прилагаемом файле нумерация символов начинается с нуля.

Подход к решению задания 24
По любому надо найти все индексы начал числа "XXXVIII"
Затем понять, что нас интересуют все нечетные числа, то есть и просто "палочки" (I),
а нужный ответ должен быть единственным.

если индекс начала искомого числа отстоит от начал "другого числа" на расстояние не меньше d, то расстояния между началами "другрих" не меньше 2d. Найдем такие начала

s = open('24.txt').read()
r = 9400
ad = [i for i in range(len(s)) if s[i : i+7] == 'XXXVIII']
bd = [(ad[i] - ad[i-1], ad[i-1], ad[i]) for i in range(1, len(ad)) if ad[i] - ad[i-1] >= 2 * r]
print(bd)

Ой-Ля-Ля
такой отрезок один (пусть [a,b])
Тогда начало нашего числа должно лежать от a+r lj b-r
Распечатаем этот фрагмент

s = open('24.txt').read()
r = 9400
ad = [i for i in range(len(s)) if s[i : i+7] == 'XXXVIII']
bd = [(ad[i] - ad[i-1], ad[i-1], ad[i]) for i in range(1, len(ad)) if ad[i] - ad[i-1] >= 2 * r]
print(bd)
a = bd[0][1] + r
b = bd[0][2] - r
print(s[a : b + 7] )

Вырежем нужный кусок и посмотрим, есть ли в нем "длинные" нечетные числа
длины 6 есть пара чисел "XXXVii" и "XXXIII"
длины 5 есть "XXXIX", "XXVII',"XXIII"
проверим вначале их

from time import process_time as prt
ts = prt()
s = open('24.txt').read()
r = 3642
ad = [i for i in range(len(s)) if s[i : i+6] == 'XXVIII']
bd = [(ad[i] - ad[i-1], ad[i-1], ad[i]) for i in range(1, len(ad)) if ad[i] - ad[i-1] >= 2*r]
print(bd) #дает понять, что нужный отрезок 1 
#rm, d = ['XXXVII', 'XXXIII'], 6
rm, d = ['XXXIX', 'XXVII', 'XXIII'], 5
a, b = bd[0][1],bd[0][2]
ans = [(min(i-a, b -i), i) for i in range(a, b) if i-a >=r and b-i>= r and s[i:i + d] in rm]  
if ans : print(min(ans))
else : print(ans)  
print( prt() - ts)

s = open('24.txt').read()
ii = 6535596
jj = 6554511
wd = [i for i in range(len(s)) if s[i : i+6] == 'XXXIII' and i - ii > 94006 and i < jj]
print(wd)
ss = s[ii:jj]
print(ss.count('XXXIII'))

Attached files
17.txt
22.txt
23.txt
24.txt
26.txt
27.txt
9.txt
Zadanie_IN11_03112026.pdf
Ключи_статград_3 ноября_11р.xlsx

Печать