Примерное время на чтение статьи: 13 минут

Рассмотрим решение некоторых задач из варианта ИН2010401 (Статград 2021 № 4).

Задача 2

---

Логическая функция F задаётся выражением ¬((?∨?)→(?∧?))∧(?→?). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции  F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных  x, y, z, w.

Переменная 1	Переменная 2	Переменная 3	Переменная 4	Функция
???	???	???	???	F
	1	1	1	1
1		1		1
		1	1	1

В ответе напишите буквы  x, y, z, w; в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Переменная 1	Переменная 1	Функция
???	???	F
0	1	0

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

Решение. Поскольку пока не известно, в каком столбце заголовка стоит какая переменная, дадим им произвольные имена по порядку, например a, b, c, d. После чего подставим их в функцию F и отобразим только строки, соответствующие значению F=1. Рассмотрим два варианта решения:

# Способ 1 (без использования библиотеки itertools)
print('a b c d')
for a in range(2):
    for b in range(2):
        for c in range(2):
            for d in range(2):
                if (not ((a or b) <= (c and d))) and (a <= d):
                    print(a, b, c, d)

# Способ 2 (с использованием функции product библиотеки itertools)
from itertools import product

def condition(x, y, z, w):
    return (not ((x or y) <= (z and w))) and (x <= w)

print('a b c d')
rec = list(product('01', repeat=4))
for a in rec:
    if condition(int(a[0]), int(a[1]), int(a[2]), int(a[3])) == 1:
        print(int(a[0]), int(a[1]), int(a[2]), int(a[3]))

Результат работы программы:

a b c d
0 1 0 0
0 1 0 1
0 1 1 0
1 0 0 1
1 1 0 1

Ответ: zxy

Задача 5

---

Алгоритм получает на вход натуральное число ?>1 и строит по нему новое число ? следующим образом:

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

Пример. Дано число ?=19. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 10011.
2. В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.
3. В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.
4. Результат работы алгоритма ?=153.

При каком наименьшем исходном числе ?>99 в результате работы алгоритма получится число, кратное 4?

def modify(st):
    (k0, k1)  = (st.count('0'), st.count('1'))
    if k0 == k1:
        st = st + st[-1]
    elif k0 > k1:
        st = st + '1'
    else:
        st = st + '0'
    return st

N = 99
while True:
    strN = bin(N)[2:]
    for _ in range(3):
        strN = modify(strN)
    R = int(strN, 2)
    if N > 99 and R % 4 == 0:
        print(N);
        break
    N += 1

Ответ: 103

Задание 6

---

Определите, при каком наименьшем введённом значении переменной ? программа выведет число 11. Для Вашего удобства программа представлена на двух языках программирования.

def alg(s):
    s = 10 * s + 5
    n = 1
    while s < 2021:
        s = s + 2 * n
        n = n + 1
    return n == 11

s = 1
while True:
    if alg(s):
        print(s);
        break;
    s += 1

Ответ: 191

Задание 7

---

В информационной системе хранятся изображения размером 1024×768 пикселей. Методы сжатия изображений не используются. Каждое изображение дополняется служебной информацией, которая занимает 1280 Кбайт. Для хранения 2048 изображений потребовалось 4 Гбайт. Сколько цветов использовано в палитре каждого изображения?

for B in range(1, 24):
    v = 2048 * (1024 * 768  * B + 1280 * 2**13) / (2 ** 33)
    if v == 4:
        print(2**B)

Ответ: 256

Задача 8

---

Вероника составляет 3-буквенные коды из букв В,Е,Р,О,Н,И,К,А, причём буква В должна входить в код ровно один раз. Все полученные коды Вероника записала в алфавитном порядке и пронумеровала. Начало списка выглядит так:

1. ААВ
2. АВА
3. АВЕ
4. …

На каком месте будет записан первый код, не содержащий ни одной буквы А?

from itertools import product

lstAll = list(product('ВЕРОНИКА', repeat=3))
lst = []
for item in lstAll:
    if item.count('В') == 1:
        lst.append(''.join(item))
lst.sort()
for i in range(0, len(lst)-1):
    if not 'А' in lst[i]:
        print(i + 1)
        break

Ответ: 23

Задание 11

---

Каждый объект, зарегистрированный в информационной системе, получает уникальный код из 14 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 79 байт для хранения содержательной информации. Сколько байтов потребуется для хранения данных (код и содержательная информация) о 30 объектах? В ответе запишите только целое число – количество байтов.

part_1 = 14 * 6    # 26 заглавных латинских букв и 10 цифр (36 комбинаций)  потребуют 6 бит
if part_1 / 8 == part_1 // 8:
    kod = part_1 // 8 
else:
    kod = part_1 // 8 + 1

v = (kod + 79) * 30
print(v)

Ответ: 2700

Задание 14

---

Значение выражения 729⁷+3¹⁶–18 записали в системе счисления с основанием 9. Сколько раз в этой записи встречается цифра 0?

N = 729**7 + 3**16 - 18
k = 0 
while N > 0:
    if N % 9 == 0:
        k += 1
    N = N // 9 
print(k)

Ответ: 14

Задание 15

---

Для какого наименьшего натурального числа ? формула ДЕЛ(?,45)∧(ДЕЛ(750,?)→(¬ДЕЛ(?,?)→¬ДЕЛ(120,?))) тождественно истинна, то есть принимает значение 1 при любом натуральном ??

def Del(n, m):
    return n % m == 0

def condition(x, A):
    return Del(A, 45) and (Del(750, x) <= ((not Del(A, x)) <= (not Del(120, x))))

for A in range(1, 10000):
    Ok = True   # для этого А все x хорошие
    for x in range(1, 1000000+1):
        if not(condition(x, A)):
            Ok = False
            break
    if Ok:
        print(A)
        break

Ответ: 90

Задача 16

---

Обозначим через ???(?,?) остаток от деления натурального числа ? на натуральное число ?. Алгоритм вычисления значения функции ?(?), где ? – целое неотрицательное число, задан следующими соотношениями:

• ?(0)=0;
• ?(?)=?(?/3), если ?>0 и при этом ???(?,3)=0;
• ?(?)=???(?,3)+?(?–???(?,3)), если ???(?,3)>0.

Назовите минимальное значение ?, для которого ?(?)=11.

def F(n):
    if n == 0:
        return 0
    elif n > 0 and n % 3 == 0:
        return F(n // 3)
    elif n % 3 > 0:
        return n % 3 + F(n - (n % 3))

n = 0      # n — целое неотрицательное число
while True:
    if F(n) == 11:
        print(n)
        break
    n += 1

Ответ: 485

Задача 17

---

Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители – 2, 3 и 5), а число 12 – нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [10001;50000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

def PrimeDelThree(n):
    SetPrimeDel = set()
    prime = True
    for d in range(2, n+1):
        while n % d == 0:
            SetPrimeDel.add(d)
            prime = False
            n = n // d
        if n == 1:
            break
        else:
            if (d*d>n) and prime:
                break  
    if prime:
        SetPrimeDel.add(n)
    return len(SetPrimeDel)==3

(count, mn) = (0, 50_000)
for n in range (50_000, 10001-1, -1):
    if PrimeDelThree(n):
        count += 1
        mn = n
print(count, mn)

Ответ: 15652 10002

Задача 22

---

Ниже записана программа, которая вводит натуральное число ?, выполняет преобразования, а затем выводит два числа. Укажите наименьшее возможное значение ?, при вводе которого программа выведет числа 3 и 10.

def alg(x):
    k = x % 9
    a, b = 0, 0
    while x > 0:
        d = x % 9
        if d == k:
            a = a + 1
        b = b + d
        x = x // 9
    return (a, b)

x = 1
while True:
    if alg(x) == (3, 10):
        print(x)
        break
    x += 1

Ответ: 874

Задача 23

---

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

1. Прибавить 1
2. Умножить на 2
3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 2 в число 36, и при этом траектория вычислений содержит число 12 и не содержит числа 30?

def numProg(start, x):
    if x < start or x == 30:
        return 0
    if x == start:
        return 1
    k = numProg(start, x-1)
    if x % 2 == 0:
        k += numProg(start, x//2)
    if x % 3 == 0:
        k += numProg(start, x//3)
    return k

# Умножаем количество маршрутов 2->12 на 12->36 (комбинаторика)
print(numProg(2, 12) * numProg(12, 36))

Ответ: 60

Задача 24

---

Текстовый файл содержит строки различной длины. Общий объём файла не превышает 1 Мбайт. Строки содержат только заглавные буквы латинского алфавита (???…?).

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

Пример. Исходный файл:

GIGA
GABLAB
AGAAA

В этом примере в первой строке две буквы G, во второй и третьей – по одной. Берём вторую строку, т. к. она находится в файле раньше. В этой строке чаще других встречаются буквы A и B (по два раза), выбираем букву B, т. к. она позже стоит в алфавите. В ответе для этого примера надо записать B.

# С помощью списка
f = open('./Data/24/ИН2010401.txt')
minG = 1_000_000_000
for stroka in f:
    kcurrG = stroka.count('G')
    if kcurrG < minG:
        minG, s = kcurrG, stroka
f.close()

cnt = [0]*26
for i in range(0, len(s) - 1):
    cnt[ord(s[i]) - ord('A')] += 1

maxCount = 0
maxi = 0

for i in range(len(cnt)):
    if cnt[i] >= maxCount:
        maxCount = cnt[i]
        maxi  = i
print(chr(maxi  + ord('A')))

# С помощью словаря
f = open('./Data/24/ИН2010401.txt')
minG = 1_000_000_000
for stroka in f:
    kcurrG = stroka.count('G')
    if kcurrG < minG:
        minG, s = kcurrG, stroka
f.close()

D = {}
for c in s:
    if c in D:
        D[c] += 1
    else:
        D[c] = 1

mx = max(D.values())
ans = []
for key, value in D.items():
    if mx == value:
        ans.append(key)
ans.sort()
print(ans[-1])

Ответ: T

Задача 25

---

Найдите все натуральные числа, принадлежащие отрезку [35000000;40000000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.

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

def isPrime(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

(a, b) = (35_000_000, 40_000_000)
for n in range (a, b+1):
    x = n
    while x % 2 == 0:
        x = x // 2    # Убираем все четные делители
    if x ** 0.25 == int(x ** 0.25) and isPrime(x ** 0.25):
        print(n)
    n += 1

Ответ: 35819648; 38950081; 39037448; 39337984

Задача 26

---

В текстовом файле записан набор натуральных чисел, не превышающих 10⁹. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар.

Входные данные Первая строка входного файла содержит целое число ? – общее количество чисел в наборе. Каждая из следующих ? строк содержит одно число.

Пример входного файла

6
3
8
14
11
2
17

В данном случае есть две подходящие пары: 8 и 14 (среднее арифметическое 11), 14 и 2 (среднее арифметическое 8). В ответе надо записать числа 2 и 11. В ответе запишите два целых числа: сначала количество пар, затем наибольшее среднее арифметическое.

# Линейный поиск (работает долго)
data = list(map(int, open(r'./Data/26/ИН2010401.txt').read().splitlines()))[1:]
k, mx = 0, 0
for i in range(len(data)-1):
    if data[i] % 2 == 0:
        for j in range(i + 1, len(data)):
            if data[j] % 2 == 0:
                sr = (data[i] + data[j]) // 2
                if sr in data:
                    k, mx = k + 1, max(mx, sr)
print(k, mx)

# Бинарный поиск
a = list(map(int, open(r'./Data/26/ИН2010401.txt').read().splitlines()))[1:]
a.sort()
lsts = []
for i in range(len(a) - 1):
    for j in range(i + 1, len(a)):
        if a[i] % 2 == 0 and a[j] % 2 == 0:
            s = (a[i] + a[j]) // 2
            L = i
            R = j + 1
            while L < R - 1:
                C = ( R + L) // 2
                if s < a[C]:
                    R = C
                else: 
                    L = C  
            if a[L] == s:
                lsts.append(s)
print(len(lsts), max(lsts))

Ответ: 15; 976339247

Задача 27

---

В текстовом файле записан набор натуральных чисел, не превышающих 10⁸. Гарантируется, что все числа различны. Из набора нужно выбрать три числа, сумма которых делится на 3. Какую наибольшую сумму можно при этом получить?

Входные данные Первая строка входного файла содержит целое число ? – общее количество чисел в наборе. Каждая из следующих ? строк содержит одно число.

4
5
8
14
11

В данном случае есть две подходящие тройки: 5,14,11 (сумма 30) и 8,14,11 (сумма 33). В ответе надо записать число 33.

Вам даны два входных файла (? и ?), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла ?, затем для файла ?.

data = sorted(list(map(int, open(r'./Data/27/ИН2010401-B.txt').read().splitlines()))[1:])
m01, m02, m03, m11, m12, m13, m21, m22, m23 = 0, 0, 0, 0, 0, 0, 0, 0, 0
for a in data:
    if a % 3 == 0:
        m03, m02, m01 = m02, m01, a
    if a % 3 == 1:
        m13, m12, m11 = m12, m11, a
    if a % 3 == 2:
        m23, m22, m21 = m22, m21, a
print(max(m01 + m02 + m03, m11 + m12 + m13, m01 + m11 + m21, m21 + m22 + m23))

Ответ: 2697; 299986167