Ошибка Кода

Разбор заданий, средний уровень
B. задача 2
Миша заполнял таблицу истинности логической функции F = ¬c ∧ (¬a → ¬d → ¬b), но успел заполнить лишь фрагмент из пяти различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных a, b, c, d.
Таблица истинности
Определите, какому столбцу таблицы соответствует каждая из переменных a,b,c,d.
В ответе напишите буквы a, b, c, d в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу, затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Решение
1 вариант
Для решения этой задачи мы используем вложенные циклы для перебора всех возможных комбинаций значений переменных a, b, c, и d, которые могут быть либо 0, либо 1.

Это даст нам всевозможные варианты истинности или ложности для каждой переменной.

Затем, в каждой итерации цикла, мы проверяем, выполняется ли заданное условие. Это условие включает в себя логические операции «НЕ» (not), «И» (and), «ИЛИ»(or), «ИМПЛИКАЦИЯ» (логическое следование, в python можно записать как «≤», меньше или равно, но нужно быть очень внимательным и следить за приоритетами операций).

В данной задаче необходимо (((not (a)) ≤ (not (d))) взять в дополнительные скобки, чтобы не нарушить порядок действий.

Если условие выполняется, мы выводим текущую комбинацию переменных a, b, c, и d. Важно заметить, что логические операции и сравнения нужно проводить в правильном порядке, соблюдая приоритеты, чтобы получить корректный результат.

Давайте разберем код построчно:
print("a b c d")
for a in 0,1:
    for b in 0,1:
        for c in 0,1:
            for d in 0,1:
                if (not(c) and (((not(a)) <= (not(d))) <= (not(b))))  == 1:
                    print(a, b, c, d)
2 вариант
Суть решения задачи заключается в том, чтобы определить, какой столбец в данном фрагменте таблицы истинности соответствует каждой из переменных a, b, c, d для заданной логической функции F.

Подход к решению задачи строится на следующих этапах:

  1. Прежде всего, мы определяем функцию F, чтобы затем проверить, какие комбинации переменных в таблице соответствуют значению 1 этой функции.
  2. В задаче неясно, какие переменные a, b, c, d соответствуют столбцам таблицы. Поэтому мы генерируем все возможные комбинации этих переменных для каждой строки таблицы.
  3. Для каждой комбинации мы должны убедиться, что все строки в таблице уникальны, так как в условии сказано, что фрагмент состоит из различных строк.
  4. Поскольку неизвестно, какая переменная соответствует какому столбцу, мы используем перестановки, чтобы перебрать все возможные распределения переменных по столбцам.
  5. Для каждой перестановки и каждой уникальной таблицы мы проверяем, соответствуют ли значения функции F тем, которые заданы в таблице.
  6. Если все условия выполнены, то текущая перестановка является решением задачи, и мы выводим её.

Почему мы используем такой подход? Этот метод является наиболее прямолинейным и систематическим способом найти решение. Он позволяет нам перебрать все возможные комбинации и перестановки, чтобы найти те, которые соответствуют заданной таблице истинности и функции F.

Давайте разберем код построчно:
# Импортируем нужные функции из модуля itertools
from itertools import *

# Определяем функцию f, реализующую логическую функцию F
def f(a, b, c, d):
    return (not(c) and (((not(a)) <= (not(d))) <= (not(b))))

# Генерируем все возможные комбинации значений переменных a1, a2, a3, a4, a5, a6
for a1, a2, a3, a4, a5, a6 in product([0, 1], repeat=6):
    
    # Задаем фрагмент таблицы истинности в виде списка кортежей
    table = [(a1, 0, a2, a6), (1, 0, a3, 0), (1, a4, a5, 0), (0, 0, 1, 0), (1, 0, 1, 0)]
    
    # Проверяем, что все строки в таблице уникальны
    if len(table) == len(set(table)):
        
        # Перебираем все возможные перестановки столбцов (abcd, abdc, acbd, ...)
        for p in permutations("abcd"):
            
            # Проверяем, что для данной перестановки значения F совпадают с заданными в таблице
            if [f(**dict(zip(p, r))) for r in table] == [1, 1, 1, 1, 1]:
                
                # Выводим найденную перестановку
                print("".join(p))
Ответ: dbac
C. задача 5

На вход программы подаётся натуральное число N. Программа преобразует это число в новое число R следующим образом:

  1. Преобразуется число N в его двоичное представление.
  2. Далее эта запись обрабатывается согласно следующему алгоритму:
    1. Если число N делится на 4, то к двоичной записи дописываются последние две двоичные цифры.
    2. Если число N не делится на 4, то остаток от деления переводится в двоичную систему и дописывается в конец числа.
  3. Если в результате преобразования получилось число, у которого последняя цифра равна 0, эту цифру удаляют.
Полученное число переводится в десятичную систему и выводится на экран.
Пример:
10 → 0102 → 1010102 → 101012 → 21
Определите минимальное число R, большее 213, которое может быть получено с помощью описанного алгоритма.
В ответе укажите это число в десятичной системе счисления.
Решение
Для решения этой задачи мы используем перебор:
  1. Инициализируем пустой список для хранения чисел, которые удовлетворяют заданному условию.
  2. Проходим по заданному диапазону чисел.
  3. Внутри цикла преобразуем каждое число в его двоичное представление.
  4. В зависимости от условий модифицируем это двоичное представление (например, добавляем к нему дополнительные биты или удаляем последний бит).
  5. Преобразуем модифицированное двоичное число обратно в десятичную систему.
  6. Проверяем, удовлетворяет ли полученное число заданному условию (в данном случае, больше ли оно 213). Если да, добавляем его в ранее инициализированный список.
  7. По завершении цикла находим минимальное число в этом списке и выводим его.

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

*В данной задаче использование массива действительно оправдано, потому что минимальное число, удовлетворяющее условиям, не обязательно будет первым найденным числом, которое больше 213. Это связано с тем, что преобразование числа N в число R не является монотонным. То есть, большее значение N не гарантирует большее значение R, и наоборот. Следовательно, необходимо проверить все возможные числа R в заданном диапазоне и только потом выбрать минимальное из них.

Давайте разберем код построчно:
# Инициализация пустого списка arr для хранения чисел R, которые больше 213.
# Это нужно для того, чтобы в конце найти минимальное из них.
arr = []

# Запускаем цикл for для каждого числа N в диапазоне от 1 до 299.
# Мы выбрали верхнюю границу 300 (не включительно), чтобы учесть все возможные числа R, которые могут быть больше 213.
for N in range(1, 300):
    
    # Преобразуем число N в его двоичное представление, удаляем префикс "0b", оставляя только двоичные цифры.
    n = bin(N)[2:]
    
    # Проверяем, делится ли число N на 4 без остатка.
    if N % 4 == 0:
        # Если делится, добавляем последние две двоичные цифры к числу n.
        n = n + n[-2:]
    else:
        # Если не делится, переводим остаток от деления N на 4 в двоичную систему и дописываем его к числу n.
        n = n + bin(N % 4)[2:]
        
    # Проверяем, равна ли последняя цифра двоичного числа n нулю.
    if n[-1] == "0":
        # Если равна, удаляем эту последнюю цифру.
        n = n[:-1]
    
    # Переводим полученное двоичное число n обратно в десятичную систему.
    R = int(n, 2)
    
    # Проверяем, больше ли число R 213.
    if R > 213:
        # Если больше, добавляем его в список arr.
        arr.append(R)

# Из всех чисел в списке arr выбираем минимальное.
print(min(arr))
Ответ: 216
D. задача 8
Какое количество четырехзначных чисел, записанных в восьмеричной системе счисления, начинается на цифру 3 и заканчивается на цифру 0, при условии, что все цифры числа различные и никакие две четные цифры не стоят рядом.
Решение
Для решения этой задачи мы используем перебор:
  1. Импортируем нужную функцию из стандартной библиотеки для создания всех возможных четырёхзначных комбинаций чисел в восьмеричной системе счисления.
  2. Инициализируем переменную-счетчик, которая будет хранить количество чисел, удовлетворяющих всем условиям.
  3. Используем цикл для перебора всех возможных четырёхзначных чисел в восьмеричной системе счисления.
  4. Внутри цикла проверяем каждое число на соответствие заданным условиям:
    • Начинается ли число на определенную цифру;
    • Заканчивается ли число на определенную цифру;
    • Все ли цифры в числе различны;
    • Соседние ли цифры в числе четные.
  5. Если число удовлетворяет всем этим условиям, увеличиваем счетчик на 1.
  6. В конце выводим значение счетчика.

Суть этого решения заключается в полном переборе всех возможных четырёхзначных чисел в восьмеричной системе счисления и проверке каждого из них на соответствие ряду заданных условий. После перебора всех комбинаций выводим количество чисел, которые удовлетворяют всем условиям.

Давайте разберем код построчно:
# Импортируем функцию product из библиотеки itertools
from itertools import product

# Инициализируем переменную n, которая будет хранить количество подходящих чисел
n = 0

# В цикле перебираем все возможные четырёхзначные числа в восьмеричной системе счисления
for i in product("01234567", repeat = 4):
    # Преобразуем кортеж в строку
    s = ''.join(i)
    
    # Проверяем, что число начинается на '3', заканчивается на '0' и все его цифры различны
    if s[0] == '3' and s[-1] == '0' and len(set(s)) == 4:
        
        # Заменяем все четные цифры на '0', чтобы удобнее проверять условие о соседних четных цифрах
        s = s.replace('2','0').replace('4','0').replace('6','0')
        
        # Проверяем, что в числе нет двух подряд идущих четных цифр ('00')
        if '00' not in s:
            # Увеличиваем счетчик подходящих чисел
            n += 1

# Выводим ответ
print(n)
Ответ: 15
E. задача 9
Откройте файл 9.txt, содержащий в каждой строке восемь натуральных чисел.
Вот первые строки файла 9.txt:
26 10 87 31 20 10 58 6
99 4 47 78 14 22 18 7
63 47 51 1 30 75 56 90
39 64 90 30 44 90 31 72
файл 9.txt можно открыть используя open()

Определите сумму всех чисел в строке с наименьшим номером, для чисел которой выполнены оба условия:

  1. В строке есть два числа, каждое из которых повторяется трижды, остальные два числа различны.
  2. Минимальное число в строке не повторяется.
В ответе запишите только сумму чисел в соответствующей строке.
Решение
Для решения этой задачи мы используем перебор строк:
  1. Инициализируем переменную для хранения результата.
  2. Открываем файл для построчного чтения.
  3. В цикле читаем каждую строку файла и преобразуем её в список чисел.
  4. Инициализируем словарь для подсчета количества каждого числа в текущей строке.
  5. Считаем количество каждого числа в строке и сохраняем это в словаре.
  6. Проверяем, удовлетворяет ли текущая строка заданным условиям:
    • Есть ли в строке ровно два числа, каждое из которых повторяется три раза;
    • Есть ли в строке всего четыре различных числа;
    • Встречается ли минимальное число в строке ровно один раз.
  7. Если все условия удовлетворены, сохраняем сумму чисел этой строки в переменную и прерываем цикл.
  8. Выводим результат.

Суть этого решения заключается в построчном чтении файла и анализе каждой строки на соответствие заданным условиям. Как только находится строка, удовлетворяющая всем условиям, вычисляется сумма чисел в этой строке, и поиск прекращается.

Давайте разберем код построчно:
# Инициализируем переменную result для хранения результата
result = None

# Открываем файл для чтения
with open('9.txt','r') as file:
    
    # Читаем файл построчно
    for row in file:
        
        # Разделяем числа
        str_numbers = row.split(' ')
        
        # Преобразуем строки в целые числа
        numbers = list(map(int, str_numbers))
        
        # Создаем словарь для хранения количества каждого числа в строке
        num_counts = {}
        
        # Считаем количество каждого числа в строке
        for num in numbers:
            if num in num_counts:
                num_counts[num] += 1
            else:
                num_counts[num] = 1
        
        # Проверяем условия
        if (
            list(num_counts.values()).count(3) == 2 and  # Два числа повторяются трижды
            len(num_counts) == 4 and  # Всего 4 различных числа в строке
            num_counts[min(numbers)] == 1  # Минимальное число встречается один раз
        ):
            result = sum(numbers)  # Суммируем числа в строке
            break  # Выходим из цикла, так как нашли нужную строку

# Выводим результат
print(result)
Ответ: 318
F. задача 12

Исполнитель редактор принимает на вход строку цифр и может выполнять две команды:

  1. Заменить (v, w)
    Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (333, 77) преобразует строку 333233 в строку 77233. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
  2. Нашлось (v)
    Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (733) ИЛИ нашлось (331) ИЛИ нашлось (3333)
  ЕСЛИ нашлось (733)
    ТО заменить (733, 411)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (331)
    ТО заменить (331, 24)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (3333)
    ТО заменить (3333, 7)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ 
На вход приведённой выше программе поступает строка, начинающаяся с цифры «7», а затем содержащая n цифр «3» (3 < n < 10 000).
Определите наименьшее значение n, при котором сумма цифр в строке, получившейся в результате выполнения программы, равна 64.
Решение

Для решения этой задачи мы используем метод «перебора» для нахождения минимального значения n. Суть метода заключается в следующем:

  1. Запускаем цикл, в котором переменная n принимает значения от 4 до 9999.
  2. Для каждого n создаем входную строку, состоящую из числа 7 и n чисел 3.
  3. Применяем заданную в условии программу к этой строке. При этом на каждой итерации заменяем подстроки в соответствии с заданными правилами ('733' на '411', '331' на '24', '3333' на '7').
  4. После того, как не удается больше сделать замен, проверяем, равна ли сумма всех цифр в получившейся строке числу 64.
  5. Если сумма равна 64, выводим текущее значение n и останавливаем цикл.

Таким образом, мы ищем минимальное n, при котором выполнение заданной программы приводит к строке, сумма цифр которой равна 64.

Давайте разберем код построчно:
# Определяем функцию для поиска минимального n
def find_minimum_n():
    # Перебираем все возможные значения n от 4 до 9999
    for n in range(4, 10000):
        # Формируем входную строку
        input_string = '7' + '3' * n

        # Применяем программу к входной строке
        while '733' in input_string or '331' in input_string or '3333' in input_string:
            input_string = input_string.replace('733', '411', 1)
            input_string = input_string.replace('331', '24', 1)
            input_string = input_string.replace('3333', '7', 1)

        # Проверяем, равна ли сумма цифр 64
        if sum(map(int, input_string)) == 64:
            print(n)
            break

# Вызываем функцию
find_minimum_n()
Ответ: 55
G. задача 13
В технологиях сети TCP/IP маска сети представляет собой двоичное число, указывающее, какая часть IP-адреса узла относится к адресу сети, а какая — к адресу узла в этой сети. Адрес сети определяется путем применения поразрядной конъюнкции к IP-адресу узла и маске сети.

Представьте, что в вашей сети, заданной IP-адресом 192.168.32.200 и маской сети 255.255.255.224, каждый IP-адрес ассоциируется с устройством, и каждое устройство имеет уникальный идентификатор, представленный количеством единиц в двоичной записи своего IP-адреса.

Ваша задача — определить, сколько устройств в сети имеют идентификатор, кратный 3.
Подсказка:
IP-адреса подсети и широковещательной передачи (broadcast) не могут быть использованы для устройств.
Решение

Для решения этой задачи мы используем класс ip_network из модуля ipaddress.

Основная идея состоит в следующем:

  1. Сначала создаем объект сети на основе заданного IP-адреса и маски. Этот объект будет содержать все возможные IP-адреса в этой сети.
  2. Затем начинаем перебор всех IP-адресов в этой сети.
  3. Для каждого IP-адреса переводим его в двоичную форму.
  4. Считаем количество единиц в этой двоичной форме.
  5. Проверяем, делится ли это количество на 3. Если да, увеличиваем счетчик.
  6. В конце выводим значение счетчика, которое покажет количество IP-адресов, удовлетворяющих заданному условию.

Таким образом, мы получаем количество IP-адресов в заданной сети, для которых количество единиц в двоичной записи делится на 3.

Давайте разберем код построчно:
# Импортируем класс ip_network из модуля ipaddress
from ipaddress import ip_network

# Инициализируем переменную count для подсчета количества IP-адресов
count = 0

# Создаем объект сети на основе IP-адреса и маски
net = ip_network('192.168.32.200/255.255.255.224', strict=False)

# Перебираем все IP-адреса в данной сети
for ip in net:
    # Преобразуем каждый IP-адрес в двоичную форму и считаем количество единиц
    # Проверяем, делится ли количество единиц на 3
    if f'{ip:b}'.count('1') % 3 == 0:
        # Увеличиваем счетчик, если условие выполняется
        count += 1

# Выводим ответ
print(count)

Ответ: 10
H. задача 14
Операнды арифметического выражения записаны в системе счисления с основанием 15.
ABCDy15+123y415
В записи чисел переменной y обозначена неизвестная цифра из алфавита 15-ричной системы счисления.
Определите наименьшее значение y, при котором значение данного арифметического выражения кратно 14.
Для найденного y вычислите частное от деления значения арифметического выражения на 14 и укажите его в ответе в десятичной системе счисления. Основание системы счисления указывать не нужно.
Решение

Для решения этой задачи мы используем перебор всех возможных значений для переменной y в 15-ричной системе счисления.

Основные шаги решения таковы:

  1. Запускаем цикл, в котором переменная y принимает каждое возможное значение в 15-ричной системе счисления: от '0' до 'E'.
  2. Составляем два числа в 15-ричной системе счисления, включая текущее значение y ('ABCDy' и '123y4').
  3. Переводим эти числа в 10-ричную систему счисления и складываем их.
  4. Проверяем, делится ли полученная сумма на 14 без остатка.
  5. Если делится, выводим частное от деления на 14 и завершаем цикл.

Таким образом, мы ищем такое значение y, при котором арифметическое выражение делится на 14 без остатка. Как только такое значение найдено, мы выводим результат и останавливаем поиск.

Давайте разберем код построчно:
# Перебираем все возможные значения y в 15-ричной системе счисления
for y in '0123456789ABCDE':
    
    # Вычисляем значение арифметического выражения для текущего y
    n = int(f'ABCD{y}', 15) + int(f'123{y}4', 15)
    
    # Проверяем, делится ли полученное число на 14 без остатка
    if n % 14 == 0:
        
        # Если делится, выводим частное от деления на 14
        print(n // 14)
        
        # Прекращаем перебор
        break
Ответ: 43166
I. задача 15
Для какого наименьшего целого неотрицательного числа A выражение
(2x + y < A) ∨ (y > 17) ∨ (x > y)
тождественно истинно (т.е. принимает значение 1) при любых целых неотрицательных x и y?
Решение

Для решения этой задачи мы используем перебор всех возможных комбинаций значений переменных a, x, и y для проверки заданного логического выражения.

Мы начинаем с самого маленького значения a, которое равно 0, и двигаемся вверх до 499 (данный диапазон может меняться в зависимости от чисел в функции, лучше взять с запасом). Для каждого a, мы проверяем выражение для всех комбинаций x и y в диапазоне от 0 до 499.

Такой «полный перебор» гарантирует, что мы проверим все возможные случаи. Это важно, потому что нам нужно удостовериться, что выражение истинно для всех x и y в заданном диапазоне, прежде чем сделать вывод о a. Основные шаги решения следующие:

  1. Определяем функцию f, которая принимает x, y, и a и вычисляет значение заданного логического выражения.
  2. Запускаем цикл для переменной a, которая принимает значения от 0 до 499.
  3. Внутри этого цикла для каждого a запускаем еще два вложенных цикла для x и y, которые также принимают значения от 0 до 499.
  4. Проверяем, является ли логическое выражение истинным для всех комбинаций x и y при данном a.
  5. Если выражение истинно для всех x и y, выводим значение a и останавливаем работу программы.

Таким образом, мы находим минимальное значение a, при котором заданное логическое выражение будет истинным для всех возможных значений x и y в заданном диапазоне.

Давайте разберем код построчно:
# Определение функции f, которая возвращает значение логического выражения
def f(x, y, a):
    return (2*x + y < a) or (y > 17) or (x > y)

# Перебор значений a от 0 до 499
for a in range(0, 500):
    # Проверка, является ли выражение истинным для всех x и y от 0 до 499
    if all(f(x, y, a) for x in range(0, 500) for y in range(0, 500)):
        # Вывод найденного значения a и завершение выполнения
        print(a)
        break
Ответ: 52
J. задача 16
Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(n) = 42 при n ≤ 1;
F(n) = F(n−2) + F(n−3) + n, если n > 1 и n — чётное;
F(n) = F(n−1) + F(n−3) − n в остальных случаях.
Чему равно значение функции F(99)?
Решение
1 вариант

Решение описывает рекурсивную функцию f (n), которая вычисляет значение на основе заданных условий.

Для ускорения вычислений используется декоратор @lru_cache (None), который кеширует результаты предыдущих вызовов функции, чтобы избежать повторного вычисления.

  1. Если n меньше или равно 1, функция возвращает значение 42.
  2. Если n больше 1 и чётное, функция возвращает сумму результатов вызовов f(n − 2), f(n − 3) и самого числа n.
  3. В противном случае (если n нечетное), функция возвращает разницу между результатами вызововв f(n − 1), f(n − 3) и самим числом n.
Давайте разберем код построчно:
'''
1. Функция f(n) рекурсивно вычисляет значение на основе заданных условий.
2. Декоратор lru_cache кеширует результаты, чтобы ускорить вычисления и избежать повторных вызовов.
3. В зависимости от значения n, функция может вызывать себя с разными аргументами и выполнять разные математические операции.
4. В конце функция вызывается с аргументом 99, и результат выводится на экран.
'''

# Импорт декоратора для кеширования результатов функции
from functools import lru_cache

# Применение декоратора к функции для кеширования результатов
@lru_cache(None)
def f(n):
    # Если n <= 1, возвращаем 42
    if n <= 1:
        return 42
    # Если n чётное и больше 1, возвращаем сумму результатов f(n - 2), f(n - 3) и n
    elif n > 1 and n % 2 == 0:
        return f(n - 2) + f(n - 3) + n
    # Если n нечетное, возвращаем разницу между результатами f(n - 1), f(n - 3) и n
    else:
        return f(n - 1) + f(n - 3) - n

# Выводим результат функции для n = 99
print(f(99))
2 вариант

Этот решение также представляет собой рекурсивную функцию f (n), но, в отличие от предыдущего примера, он использует глобальный список values для кеширования результатов функции, вместо использования декоратора lru_cache.

Рассмотрим код подробнее:

  1. Список values инициализируется длиной 100 с элементами None. Этот список будет использоваться для хранения вычисленных значений функции f для различных n.
  2. В функции f(n) сначала проверяется, вычислено ли уже значение для данного n (то есть является ли values[n] не None). Если значение уже вычислено, функция возвращает его.
  3. Если значение еще не вычислено, функция определяет его на основе заданных условий, как и в предыдущем примере.
  4. После вычисления значения оно сохраняется в списке values и возвращается.
Давайте разберем код построчно:
'''
1. Функция f(n) рекурсивно вычисляет значение на основе заданных условий.
2. Глобальный список values используется для кеширования результатов, чтобы ускорить вычисления и избежать повторных вызовов.
3. В зависимости от значения n, функция может вызывать себя с разными аргументами и выполнять разные математические операции.
4. После вычисления значения оно сохраняется в списке values.
5. В конце функция вызывается с аргументом 99, и результат выводится на экран.
'''
# Инициализация списка для кеширования результатов функции
values = [None] * 100

# Определение функции f(n)
def f(n):
    global values
    # Если значение для n уже вычислено, возвращаем его
    if values[n] != None:
        return values[n]
    # Если n <= 1, значение равно 42
    if n <= 1:
        value = 42
    # Если n чётное и больше 1, вычисляем значение на основе f(n - 2), f(n - 3) и n
    elif n > 1 and n % 2 == 0:
        value = f(n - 2) + f(n - 3) + n
    # Если n нечетное, вычисляем значение на основе f(n - 1), f(n - 3) и n
    else:
        value = f(n - 1) + f(n - 3) - n
    # Сохраняем вычисленное значение в список values
    values[n] = value
    return value

# Выводим результат функции для n = 99
print(f(99))
Ответ: 604232317753149
K. задача 17
В файле содержится последовательность натуральных чисел, каждое из которых не превышает 5 000.
Вот первые строки файла 17.txt:
2185
2781
3045
1493
файл 17.txt можно открыть используя open()
Определите количество четверок элементов последовательности, в которых ровно два из четырёх элементов больше 1000, а сумма элементов четверки не больше максимального элемента последовательности, оканчивающегося на 47.
Гарантируется, что в последовательности есть хотя бы одно число, оканчивающееся на 47.

В ответе запишите количество найденных четвёрок чисел, затем максимальную из сумм элементов таких четвёрок.

Пример вывода:
1234 11111
В данной задаче под четверкой подразумевается четыре идущих подряд элемента последовательности.
Решение
Для решения этой задачи мы используем несколько ключевых шагов:
  1. Сначала читаем все числа из файла и сохраняем их в списке.
  2. Находим максимальное число в этой последовательности, которое оканчивается на 47. Это число будет использоваться для сравнения с суммами четверок чисел.
  3. Затем перебираем все возможные «четверки» чисел в последовательности. «Четверкой» называется группа из четырех подряд идущих чисел.
  4. Для каждой такой четверки проверяем два условия:
    • Ровно два числа в четверке больше 1000.
    • Сумма чисел в четверке не больше найденного максимального числа, оканчивающегося на 47.
  5. Если оба условия выполняются, увеличиваем счетчик четверок и обновляем максимальную сумму, если текущая сумма четверки больше уже найденной максимальной суммы.

Такой подход эффективен, потому что мы делаем только один проход по списку чисел, сохраняя при этом всю нужную информацию для ответа на вопросы задачи. В итоге, мы получаем количество четверок, удовлетворяющих заданным условиям, и максимальную сумму среди этих четверок.

Давайте разберем код построчно:
# Путь к файлу
file_path = '17.txt'
# Чтение чисел из файла и преобразование их в список целых чисел
with open(file_path, 'r') as f:
    nums = list(map(int, f.read().split()))

# Находим максимальное число в последовательности, которое оканчивается на 47
max_47 = max(x for x in nums if x % 100 == 47)

# Инициализируем переменные для подсчета количества четверок и максимальной суммы
cnt = 0
max_sum = 0

# Перебираем все четверки чисел в последовательности
for i in range(len(nums) - 3):
    quartet = nums[i:i + 4]
    
    # Проверяем условия для каждой четверки:
    # 1) ровно два элемента больше 1000
    # 2) сумма элементов не больше max_47
    if sum(x > 1000 for x in quartet) == 2 and sum(quartet) <= max_47:
        cnt += 1
        max_sum = max(max_sum, sum(quartet))

# Выводим результат
print(cnt, max_sum)
Ответ: 154 3946
L. задача 19

Алиса и Боб играют в игру с двумя кучами монет. Алиса ходит первой. За один ход игрок может либо добавить одну монету в одну из куч (по своему выбору), либо умножить количество монет в одной из куч на два.

Игра завершается, когда суммарное количество монет в кучах становится не менее 122.

В начальный момент в первой куче 22 монеты, во второй куче —  S монет 1 ≤ S ≤ 99.

Известно что Боб выиграл своим первых ходом, после неудачного хода Алисы.

Найдите минимальное значение S при котором это возможно.
Решение

Для решения этой задачи мы используем рекурсивную функцию, которая моделирует ходы в игре между Алисой и Бобом.

Основная идея решения:

  1. Функция принимает три аргумента: a, b, и m. Здесь a и b — это количество камней в двух кучах, а m — номер хода.
  2. Сначала проверяем, достигла ли сумма камней в кучах значения 122 или более. Если да, определяем, кто выиграл, исходя из номера хода.
  3. Затем, в зависимости от того, чей ход сейчас (Алисы или Боба), делаем рекурсивный вызов функции для всех возможных ходов: увеличение одной из куч на 1 или удвоение камней в одной из куч.
  4. Для каждого такого хода смотрим, кто выиграет, если играть оптимально. Если это ход Боба, ему нужно, чтобы хотя бы один из рекурсивных вызовов возвращал True (он выигрывает).

В итоге, мы ищем минимальное значение S, при котором Боб выигрывает своим первым ходом после ошибочного хода Алисы. Это делается с помощью перебора возможных начальных значений S и проверки исхода игры для каждого из них.

Давайте разберем код построчно:
# Определение рекурсивной функции f, которая моделирует игру
def f(a, b, m):
    # Проверка, достигла ли сумма двух куч 122 или более
    if a+b >= 122:
        # Если это ход Боба, он выигрывает
        return m % 2 == 0
    # Если это ход Алисы и сумма еще не достигла 122, она проигрывает
    if m == 0:
        return 0
    # Рекурсивный вызов функции для всех возможных ходов
    h = [f(a+1, b, m-1), f(a * 2, b, m-1), f(a, b+1, m-1), f(a, b*2, m-1)]
    # Если это ход Боба, он выигрывает, если хотя бы один из рекурсивных вызовов возвращает True
    # Если это ход Алисы, она проигрывает, если хотя бы один из рекурсивных вызовов возвращает True
    return any(h) if (m-1) % 2 == 0 else any(h)

# Поиск минимального значения S, при котором Боб выигрывает своим первым ходом
print(min([s for s in range(1, 100) if f(22, s, 2)]))
Ответ: 25
M. задача 20

Алиса и Боб играют в игру с двумя кучами монет. Алиса ходит первой. За один ход игрок может либо добавить одну монету в одну из куч (по своему выбору), либо умножить количество монет в одной из куч на два.

Игра завершается, когда суммарное количество монет в кучах становится не менее 122.

В начальный момент в первой куче 22 монеты, во второй куче — S монет 1 ≤ S ≤ 99.

Найдите минимальное значение S, при котором у Алисы есть выигрышная стратегия, причём одновременно выполняются два условия:

  • Алиса не может выиграть за один ход;
  • Алиса может выиграть своим вторым ходом независимо от того, как будет ходить Боб.
Решение

Ход решения для данной задачи отличается от задачи 19 тем, что на этот раз оба игрока играют оптимально (нет неудачных ходов).

Также необходимо добавить дополнительное условие:

  1. Алиса не может выиграть за один ход. Это проверяется функцией f(22,s,1), которая должна вернуть False.
  2. Алиса может выиграть, если у неё это второх ход. Это проверяется функцией f(22,s,3), которая должна вернуть True.

В остальном решение идентичное и подробно расписано в 19 задаче.

Давайте разберем код построчно:
# Функция f рекурсивно решает задачу для заданных состояний куч a и b и ходов m.
# Возвращает True, если для игрока, который ходит m-м, есть выигрышная стратегия.
def f(a, b, m):
    # Если сумма монет в кучах больше или равна 122, то проверяем, выигрывает ли текущий игрок.
    if a+b >= 122:
        return m % 2 == 0
    # Если ходов больше нет, то текущий игрок проигрывает.
    if m == 0:
        return 0
    # Вычисляем возможные ходы для текущего игрока и храним их в списке h.
    h = [f(a+1, b, m-1), f(a * 2, b, m-1), f(a, b+1, m-1), f(a, b*2, m-1)]
    # Если следующий ход принадлежит противнику, то текущий игрок выигрывает, если противник проигрывает хотя бы одной стратегии.
    # Иначе текущий игрок выигрывает только если противник проигрывает всем стратегиям.
    return any(h) if (m-1) % 2 == 0 else all(h)

# Ищем минимальное значение S, при котором Алиса не может выиграть за один ход, но может выиграть своим вторым ходом.
print(min([s for s in range(1, 100) if not f(22, s, 1) and f(22, s, 3)]))
Ответ: 33
N. задача 21

Алиса и Боб играют в игру с двумя кучами монет. Алиса ходит первой. За один ход игрок может либо добавить одну монету в одну из куч (по своему выбору), либо умножить количество монет в одной из куч на два.

Игра завершается, когда суммарное количество монет в кучах становится не менее 122.

В начальный момент в первой куче 22 монеты, во второй куче — S монет 1 ≤ S ≤ 99.

Найдите значение S, при котором одновременно выполняются два условия:

  • у Боба есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Алисы;
  • у Боба нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение

Ход решения для данной задачи отличается от задачи 20 тем, что:

  1. Боб не может гарантированно выиграть своим первым ходом. Это проверяется функцией f(22,s,2), которая должна вернуть False.
  2. Боб может выиграть, если у него будет два хода. Это проверяется функцией f(22,s,4), которая должна вернуть True.

В остальном решение идентичное и подробно расписано в 19 задаче.

Давайте разберем код построчно:
# Функция f рекурсивно решает задачу для заданных состояний куч a и b и ходов m.
# Возвращает True, если для игрока, который ходит m-м, есть выигрышная стратегия.
def f(a, b, m):
    if a+b >= 122:  # Проверка условия окончания игры
        return m % 2 == 0  # Проверка, выигрывает ли текущий игрок
    if m == 0:  # Проверка наличия ходов
        return 0  # Если ходов нет, игрок проигрывает
    # Рекурсивный перебор возможных ходов для текущего состояния
    h = [f(a+1, b, m-1), f(a * 2, b, m-1), f(a, b+1, m-1), f(a, b*2, m-1)]
    # Логика определения выигрыша или проигрыша для текущего игрока
    return any(h) if (m-1) % 2 == 0 else all(h)

# Ищем значение S, при котором Боб может выиграть первым или вторым ходом, но не может гарантированно выиграть первым ходом.
print(*[s for s in range(1, 100) if not f(22, s, 2) and f(22, s, 4)])

Ответ: 48
С. задача 22
В файле 22.txt содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.

Информация о процессах представлена в виде txt файла.

В первом столбце указан идентификатор процесса (ID), во втором столбце — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то указано значение 0.

Вот первые строки файла 22.txt:
1 225 0
2 192 0
3 201 2;1
4 117 3
5 217 1;4;3
файл 22.txt можно открыть используя open()
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Решение
Для решения этой задачи мы используем словарь для хранения минимального времени выполнения каждого процесса.

Изначально в этом словаре есть только начальный процесс с временем выполнения равным нулю.

Мы также создаём список, в который считываем все данные о процессах и их зависимостях.

Перебираем процессы до тех пор, пока не найдены минимальные времена выполнения для всех процессов. В каждом проходе этого цикла мы просматриваем все процессы и проверяем, известно ли нам уже минимальное время выполнения для всех их зависимостей. Если известно, мы вычисляем и сохраняем минимальное время выполнения для текущего процесса как сумму его собственного времени выполнения и максимального из минимальных времен выполнения его зависимостей.

В конце программы мы выводим максимальное из найденных минимальных времен выполнения.

Давайте разберем код построчно:
d = {'0': 0}  # Словарь для хранения минимального времени выполнения для каждого процесса
data = []  # Список для хранения информации о каждом процессе

# Чтение данных из файла и преобразование их в удобный для работы формат
for s in open('22.txt'):
    data.append(s.replace(';', ' ').split())

# Цикл, который будет выполняться до тех пор, пока для всех процессов не будет найдено минимальное время выполнения
while len(d) != len(data) + 1:
    for s in data:
        # Проверка, известно ли минимальное время выполнения для всех зависимостей текущего процесса
        if all(sub in d for sub in s[2:]):
            # Вычисление и сохранение минимального времени выполнения для текущего процесса
            d[s[0]] = int(s[1]) + max(d[sub] for sub in s[2:])

# Вывод максимального значения среди всех минимальных времен выполнения процессов
print(max(d.values()))
Ответ: 5551
P. задача 23
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

  1. Прибавить 2
  2. Умножить на 2
  3. Возвести в куб

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 200, при этом траектория вычислений не содержит числа 15, но содержит число 50?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ACB при исходном числе 3 траектория состоит из чисел 5, 125, 250.
Решение
Для решения этой задачи мы используем рекурсивный метод.
В данном случае, функция рекурсивно ищет количество способов, чтобы перейти от числа x до числа y через определенные операции (прибавление 2, умножение на 2 и возведение в куб), причем с условием, что если в какой-то момент число становится равным 15, этот способ не считается.

  1. Если x равно 15, мы сразу возвращаем 0, потому что такой вариант нам не подходит.
  2. Если x стало больше или равно y, мы проверяем, равны ли они. Если равны, то это один из допустимых способов.
  3. Далее, функция вызывает сама себя три раза: один раз после прибавления 2 к x, второй раз после умножения x на 2, и третий раз после возведения x в куб. Результаты этих трех вызовов складываются, чтобы получить общее количество допустимых способов.

На самом деле, этот процесс повторяется для каждого рекурсивного вызова, пока x не станет равным или большим y.

В конце мы просто перемножаем количество способов для двух разных интервалов чисел (от 3 до 50 и от 50 до 200) для получения итогового ответа.

Давайте разберем код построчно:
# Функция f рекурсивно считает количество программ от числа x до числа y
def f(x, y):
    # Если на каком-то этапе x стало равным 15, такая программа нам не подходит
    if x == 15: 
        return 0
    # Если x достиг или превысил y, проверяем, равны ли они
    if x >= y: 
        return x == y
    # Рекурсивно вызываем функцию для всех трех операций и суммируем результаты
    return f(x + 2, y) + f(x * 2, y) + f(x ** 3, y)

# Считаем количество программ, которые переходят от 3 к 50, и от 50 к 200
# Перемножаем эти количества для получения итогового ответа
print(f(3, 50) * f(50, 200))
Ответ: 1596
Q. задача 24
Текстовый файл 24.txt состоит из символов A, B, C, D, E.
Определите максимальное число идущих подряд символов в файле, удовлетворяющих условию: среди выбранных символов не встречается символа «A», который идёт раньше символа «B».
Например, подряд идущие символы «BCBAD» подходят под это условие, а последовательность символов «DCACBB» — не подходит. Для выполнения этого задания следует написать программу.
Начало файла 24.txt
CDBABBEBEB...
файл 24.txt можно открыть используя open()
Решение
Для решения этой задачи мы используем перебор всех возможных подстрок в данной строке.
Идея заключается в том, чтобы находить подстроки, которые начинаются с каждого символа исходной строки, и продолжаются до того момента, пока не встретятся определенные условия. В данном случае, условиями являются символы 'A' и 'B'.

  1. Сначала инициализируем переменную, которая будет хранить максимальную длину подстроки.
  2. Затем перебираем каждую начальную позицию подстроки в исходной строке.
  3. Для каждой начальной позиции, мы перебираем символы, начиная с этой позиции и до конца строки.
  4. В процессе этого перебора, мы отслеживаем, встретилась ли уже буква 'A' и прерываем подстроку, если после 'A' встретилась буква 'B'.
  5. Запоминаем длину текущей подстроки и сравниваем её с максимальной найденной длиной. Если текущая длина больше, то обновляем максимальную длину.

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

Давайте разберем код построчно:
# Открываем файл и читаем его содержимое
with open('24.txt') as file:
    content = file.read()
max_len = 0  # Инициализируем переменную для хранения максимальной длины подстроки

# Перебираем каждую начальную позицию подстроки в файле
for i in range(len(content)):
    encountered_A = False  # Флаг для отслеживания вхождения 'A' в подстроку
    cur_len = 0  # Переменная для хранения текущей длины подстроки

    # Перебираем символы, начиная с i-того элемента
    for j in range(i, len(content)):
        if content[j] == 'A':  # Если встретилась 'A', устанавливаем флаг в True
            encountered_A = True
        if content[j] == 'B' and encountered_A:  # Если встретилась 'B' после 'A', прерываем цикл
            break
        cur_len += 1  # Увеличиваем текущую длину подстроки

    # Если текущая длина подстроки больше максимальной, обновляем максимальную длину
    if cur_len > max_len:
        max_len = cur_len

# Выводим максимальную длину подстроки
print(max_len)
Ответ: 51
R. задача 25

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

  • символ «?» означает ровно одну произвольную цифру;
  • символ « *» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 1010, найдите все числа, соответствующие маске 19?71*32?, делящиеся на 2024 без остатка.
Для каждого найденного числа выведите это число, а затем, через пробел, частное от деления этого числа на 2024.

Числа нужно выводить в порядке возрастания, в одной строке — одно число и частное от деления найденного числа на 2024.

Решение
Для решения этой задачи используется перебор чисел с шагом, равным 2024.
Это позволяет убедиться, что каждое перебираемое число делится на 2024. Затем для каждого такого числа проверяется, соответствует ли оно заданной маске. Для этого используется функция fnmatch из одноименной библиотеки Python.

Для решения этой задачи мы используем специальную функцию из библиотеки fnmatch, которая позволяет сравнивать строки с определенными «масками» или шаблонами.

  1. В цикле перебираем числа от 2024 до 10101010 с шагом 2024. (Поскольку мы ищем числа, которые должны быть кратны 2024 (это следует из условия, что мы выводим частное от деления числа на 2024), нет смысла проверять числа, которые не кратны 2024)
  2. Каждое такое число преобразуем в строку и сравниваем с заданной маской '19?71*32?'.
  3. Эта маска означает, что первые две цифры должны быть 19, затем любая цифра (знак ?), затем 71, затем любое количество цифр (знак *), и наконец 32 и опять любая цифра (знак ?).
  4. Если число удовлетворяет этой маске, выводим его и результат его деления на 2024.

Таким образом, мы находим все числа в заданном диапазоне, которые соответствуют определенному шаблону, и выводим их вместе с частным от деления на 2024.

Давайте разберем код построчно:
from fnmatch import fnmatch  # Импортируем все функции из библиотеки fnmatch

# Перебираем числа от 2024 до 10^10 с шагом 2024
for n in range(2024, 10**10 + 1, 2024):
    # Проверяем, соответствует ли текущее число маске '19?71*32?'
    if fnmatch(str(n), '19?71*32?'):
        # Если да, выводим число и частное от деления его на 2024
        print(n, n//2024)
Ответ:
19171328 9472
191717328 94722
198716320 98180
1917177328 947222
1937164328 957097
1947199320 962055
1957151328 966972
1967186320 971930
1977138328 976847
1987173320 981805
1997125328 986722
S. задача 26
В магазине для упаковки подарков имеется N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. Одну коробку можно поместить в другую, если длина её стороны ровно на 1 единицу меньше длины стороны другой коробки.
Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок.
Размер подарка позволяет поместить его в самую маленькую коробку.
Формат ввода
В первой строке входного файла 26.txt находится число N — количество коробок в магазине (натуральное число, не превышающее 10000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10000), каждое — в отдельной строке.
Типовой пример организации данных во входном файле:
5
43
44
41
40
39
файл 26.txt можно открыть используя open()
Пример входного файла 26.txt приведён для пяти коробок и случая, когда для упаковки «матрёшкой» длина стороны одной коробки должна быть ровно на 1 единицу меньше длины стороны другой коробки.

При таких исходных данных условию задачи удовлетворяет набор коробок с длинами сторон 39, 40, 41 и 43, 44 т. е. максимальное количество коробок равно 3, а длина стороны самой маленькой коробки равна 39.

Формат вывода
В ответе запишите два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе. Ответ выводи через пробел.
Решение
Для решения этой задачи мы используем перебор с отслеживанием текущей последовательности коробок.

Основная идея заключается в том, чтобы найти самую длинную последовательность коробок, которую можно использовать для упаковки подарка «матрёшкой».

  1. Сначала считываем все размеры коробок из файла и сортируем их по размеру.
  2. Затем инициализируем переменные для хранения максимального количества коробок и минимального размера коробки.
  3. Перебираем все коробки и смотрим, можно ли текущую коробку положить в предыдущую (размеры отличаются на 1).
  4. Если можно, увеличиваем счетчик текущего количества коробок в последовательности и обновляем минимальный размер коробки.
  5. Если не можем продолжить текущую последовательность, начинаем считать заново.

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

Давайте разберем код построчно:
 # Чтение данных из файла
with open("26.txt", 'r') as file:
    N = int(file.readline().strip())  # Читаем количество коробок
    box_sizes = sorted([int(file.readline().strip()) for _ in range(N)])  # Читаем размеры коробок и сортируем их

# Инициализация переменных
max_count = 0  # Максимальное количество коробок для упаковки подарка
min_size = box_sizes[0]  # Инициализация минимального размера коробки

# Цикл для поиска максимального количества коробок и минимального размера коробки
count = 1  # Текущее количество коробок в последовательности
for i in range(1, N):
    if box_sizes[i] - box_sizes[i - 1] == 1:  # Если разница между текущим и предыдущим размером равна 1
        count += 1  # Увеличиваем счетчик коробок в последовательности
        min_size = min(min_size, box_sizes[i - count + 1])  # Обновляем минимальный размер коробки
        max_count = max(max_count, count)  # Обновляем максимальное количество коробок
    else:
        count = 1  # Сбрасываем счетчик коробок

# Вывод результата
print(max_count, min_size)
Ответ: 55 53
T. задача 27_А
На вход программы поступает последовательность из целых чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была минимальной и делилась на 997, а также её длину. Если таких подпоследовательностей несколько, выбрать такую, у которой длина больше.
Входные данные
Дан входной файл 27_A.txt, который содержит в первой строке количество чисел 𝑁(2 ≤ 𝑁 ≤ 108). В каждой из последующих N строк записано одно целое число, не превышающее по модулю 100 000. Программа должна вывести длину найденной последовательности.
Пример организации исходных данных во входном файле:
8
1
99
3
97
53
50
100
48
файл 27_A.txt можно открыть используя open()
Для делителя 100 при указанных входных данных значением искомой суммы должно быть число 100 (1+99, 3+97 или 100). Следовательно, ответ на задачу — 2.
В ответе укажите длину искомой подпоследовательности для файла 27_A.txt.
Решение
Для решения этой задачи мы используем перебор всех возможных подпоследовательностей чисел в исходном списке.

Задача состоит из двух частей:

  1. Найти минимальную сумму подпоследовательности, которая делится на заданный делитель.
  2. Найти максимальную длину подпоследовательности с найденной минимальной суммой.

1-я часть:

  • Сначала открываем файл и считываем все числа.
  • Инициализируем переменную для хранения минимальной суммы подпоследовательности.
  • Затем, перебираем все возможные подпоследовательности и проверяем, делится ли их сумма на заданный делитель.
  • Если делится, сравниваем сумму с текущей минимальной суммой и обновляем её при необходимости.

2-я часть:

  • Используем похожий перебор всех подпоследовательностей.
  • На этот раз, для каждой подпоследовательности проверяем, равна ли её сумма найденной минимальной сумме.
  • Если равна, сравниваем длину этой подпоследовательности с текущей максимальной и обновляем максимальную длину при необходимости.

В итоге, мы получим два ответа: минимальную сумму подпоследовательности, которая делится на заданный делитель, и максимальную длину подпоследовательности с этой суммой.

Этот метод хорошо подходит для небольших данных, но может быть неэффективным для больших объёмов, как указано в условии для варианта «B».

Давайте разберем код построчно:
 # Открываем файл и считываем числа
with open('27_A.txt') as f:
    n, *nums = [int(num) for num in f.read().strip().split()]
    div = 997  # заданный делитель

# Инициализация переменной для хранения минимальной суммы
total_min = float('inf')

# Перебор всех подпоследовательностей
for left in range(0, n):  # начало подпоследовательности
    for right in range(left, n):  # конец подпоследовательности
        sub = nums[left:right + 1]  # текущая подпоследовательность
        # Проверка кратности суммы
        if sum(sub) % div == 0:
            total_min = min(sum(sub), total_min)  # обновление минимальной суммы
print(total_min)

# Инициализация переменной для хранения максимальной длины
l_max = -float('inf')

# Перебор всех подпоследовательностей для нахождения максимальной длины
for left in range(0, n):  # начало подпоследовательности
    for right in range(left, n):  # конец подпоследовательности
        sub = nums[left:right + 1]  # текущая подпоследовательность
        # Проверка суммы
        if sum(sub) == total_min:
            l_max = max(len(sub), l_max)  # обновление максимальной длины
print(l_max)
Ответ: 159
U. задача 27_В
На вход программы поступает последовательность из целых чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была минимальной и делилась на 997, а также её длину. Если таких подпоследовательностей несколько, выбрать такую, у которой длина больше.
Вводные данные
Дан входной файл 27_B.txt, который содержит в первой строке количество чисел 𝑁(2 ≤ 𝑁 ≤ 108). В каждой из последующих N строк записано одно целое число, не превышающее по модулю 100 000. Программа должна вывести длину найденной последовательности.
Пример организации исходных данных во входном файле:
8
1
99
3
97
53
50
100
48
файл 27_B.txt можно открыть используя open()
Для делителя 100 при указанных входных данных значением искомой суммы должно быть число 100 (1+99, 3+97 или 100). Следовательно, ответ на задачу — 2.
В ответе укажите длину искомой подпоследовательности для файла 27_B.txt.
Предупреждение:
для обработки файла 27_B.txt не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Решение
Для решения этой задачи мы используем метод динамического программирования с использованием массива для хранения информации о остатках от деления сумм подпоследовательностей на заданный делитель.

Этот метод гораздо быстрее простого перебора всех подпоследовательностей.

  1. Сначала инициализируем массив, который будет хранить информацию о минимальной сумме и длине подпоследовательности для каждого возможного остатка от деления на заданный делитель.
  2. Затем делаем первый проход по массиву чисел для нахождения минимальной суммы подпоследовательности, которая делится на заданный делитель.
    • Каждый раз, когда добавляем число к текущей сумме, проверяем, можем ли мы обновить минимальную сумму, используя информацию в массиве остатков.
  3. Далее делаем второй проход по массиву чисел для нахождения максимальной длины подпоследовательности с найденной минимальной суммой.
    • Аналогично первому проходу, каждый раз обновляем информацию в массиве остатков и проверяем, можем ли мы обновить максимальную длину подпоследовательности.

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

Давайте разберем код построчно:
 # Открываем файл и считываем числа
with open('27_B.txt') as f:
    n, *nums = [int(num) for num in f.read().strip().split()]
    div = 997  # заданный делитель

# Инициализация массива для хранения информации о остатках от деления сумм
rems = [None] * div  # (sum, len)
rems[0] = (0, 0)  # инициализация для остатка 0

# Переменные для хранения текущей суммы и минимальной суммы
total = 0
total_min = float('inf')

# Первый проход: поиск минимальной суммы
for i in range(0, n):
    total += nums[i]  # обновление текущей суммы
    rem = total % div  # вычисление текущего остатка
    # Проверка и обновление минимальной суммы
    if rems[rem] != None:
        total_min = min(total_min, total - rems[rem][0])
    # Обновление информации о остатке
    if rems[rem] == None or rems[rem][0] > total or (rems[rem][0] == total and rems[rem][1] < i + 1):
        rems[rem] = (total, i + 1)

# Второй проход: поиск максимальной длины
total = 0
l_max = -float('inf')
for i in range(0, n):
    total += nums[i]
    rem = total % div
    # Проверка и обновление максимальной длины
    if rems[rem] != None:
        if total - rems[rem][0] == total_min:
            l_max = max(l_max, i + 1 - rems[rem][1])
    # Обновление информации о остатке
    if rems[rem] == None or rems[rem][0] > total or (rems[rem][0] == total and rems[rem][1] < i + 1):
        rems[rem] = (total, i + 1)

# Вывод результатов
print(total_min)
print(l_max)
Ответ: 487745
Fri Feb 09 2024 12:47:28 GMT+0300 (Moscow Standard Time)