Ответы на ЕГЭ по информатике (11 июня)

Многое совпало со вчерашним экзаменом, смотри разбор тут:

ОТВЕТЫ ЕГЭ ИНФОРМАТИКА 10 ИЮНЯ

Задание 5

Вариант 1

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

1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
   а) Если число N делится на 3, то слева дописывается “20”, а справа – “1”;
   б) Если число N не делится на 3, то остаток от деления числа N на 3 умножается на 6, переводится в троичную запись и дописывается в начало числа.
   Полученная таким образом запись является троичной записью искомого числа R.
3. Результат переводится в десятичную систему и выводится на экран.
   
   Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее, чем 210.

# Решение:

def to_3(n):
  s = ""
  while n > 0:
  s += str(n% 3)
  n // = 3
return s[:-1]

for n in range(1, 1000):
  n3 = to_ 3(n)
  if n % 3 == 0:
  n3 = '20' + n3 + '1'
else:
  n3 = to_3((n% 3) *6) + n3
R = int(n3, 3)
if R > 210:
  print(n)
  break

# Ответ: 9

Вариант 2

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

1. Строится троичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то слева
дописывается «1», а справа – «02»;
б) если число N на 3 не делится, то остаток от деления умножается на 4, переводится в троичную запись и дописывается в начало числа.

Полученная таким образом запись является троичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 11 = 102₃, результатом является число 10222₃ = 107, а для исходного числа 12 = 110₃ результатом является число 11100₃ = 353.

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее чем 135.

В ответе запишите это число в десятичной системе счисления.

Ответ: 6

Задание 7

Делают фото с разрешением 1920х1080 пикселей, используя палитру в 2²² цветов. Потом сжимают файлы до 1280х1024 пикселей. Сколько КБайт экономят при сжатии для 120 фото.

# Решение: 

from math import ceil, log2

x = ceil(log2(2 ** 22))
i1 = 1920 * 1080 * x
i2 = 1280 * 1024 * x
res = 120 * (i1 - i2) / (2**13)
print(res)

Задание 11

На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 8164-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 835 серийных номеров отведено более 156 Кбайт памяти. Определите минимально возможную длину серийного номера. В ответе запишите только целое число.

# Решение:

from math import *
for n in range(1, 10000):
  i = ceil(log2(10 + 26 + 8164))
  v = ceili* n)/8)
  if v *835 > 156 * 2**10:
   print(n)
   break

# Ответ: 110

Задание 12

Вариант 1

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

1. заменить (v, w)
2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Дана программа для Редактора:

ПОКА нашлось (055) ИЛИ нашлось (65) ИЛИ нашлось (5555)
ЕСЛИ нашлось (055)
ТО заменить (055, 56)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (65)
ТО заменить (65, 5)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (5555)
ТО заменить (5555, 000)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (00000)
ТО заменить (00000, 6)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «5», а заканчивающаяся цифрой «0» (3 < n < 2500). Определите наибольшее значение суммы числовых значений цифр в строке, которая может быть результатом выполнения данной программы. 

# Решение:

a = set() 
for n in range (4, 2500): 
    s = n * '5' + '0' 
    while ('055' in s) or ('65' in s) or ('5555' in s):
        if '055' in s:
            s = s.replace('055','56', 1)
        if '65' in s:
            s = s.replace('65','5', 1)
        if '5555' in s:
            s = s.replace('5555','000', 1)
        if '00000' in s:
            s = s.replace('00000','6', 1)

    a.add(sum(map(int, s))) 

print(max(a)) 

# Ответ: 15

Вариант 2

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

1. заменить (v, w)
2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.

Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для Редактора:
ПОКА нашлось (888) ИЛИ нашлось (44) ИЛИ нашлось (5)
ЕСЛИ нашлось (888)
ТО заменить (888, 4)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (44)
ТО заменить (44, 58)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (5)
ТО заменить (5, 8)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА

На вход приведённой выше программе поступает строка, содержащая n цифр 8. (341 < n < 500)
Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения данной программы.

# Решение:

12

res = []
for n in range(342, 500):
    s = '8' * n
    while '888' in s or '44' in s or '5' in s:
        if '888' in s:
# решение от t.me/soldaevainfo
            s = s.replace('888', '4', 1)
        if '44' in s:
            s = s.replace('44', '58', 1)
        if '5' in s:
            s = s.replace('5', '8', 1)
    sm = sum(int(i) for i in s)
    res.append(sm)

print(max(res))

# Ответ: 20

Задание 14

В выражении 32х437 + 5х2937 х обозначает некоторую цифру из алфавита системы счисления с основанием 37. Определите наименьшее значение х, при котором значение данного выражения кратно 63. Для найденного х вычислите частное от деления данного выражения на 63 и запишите его в ответе в десятичной системе счисления.

# Решение:

for x in range (37):
  first = 3*37**3+2*37**2+x*37+4
  second = 5*37**3+x*37**2+2*37+9
  summa = first + second
  if summa % 63 == 0:
   print(x, summa // 63)

# Ответ: 6901

Задание 16

Алгоритм вычисления значения функции F(n), где n — целое число, задан следующими соотношениями:

— F(n)=n при n ≤ 7;
— F(n) = G(n-3) x 3, если n < 7;
— G(n) = n при n ≤ 7;
— G(n) = G(n-1) + 4, если n > 7

Чему равно значение выражения F(43000)?

# Решение: 

from functools import *

@lru_cache()
def f(n):
    if n <= 7:
        return n
    return g(n-3) * 3
# решение от t.me/soldaevainfo
@lru_cache()
def g(n):
    if n <= 7:
        return n
    return g(n-1) + 4

for n in range(43001):
    g(n)
    f(n)

print(f(43000))

# ответ: 515901

Задание 17

В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от -100 000 до 100 000 включительно. Определите количество троек элементов последовательности, в которых хотя бы два числа являются двузначными, а квадрат суммы чисел тройки не больше максимального элемента последовательности, оканчивающегося на 33. В ответе запишите количество найденных троек, затем максимальную из сумм элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

# Решение:

f= open(17_3.txt')

digits = [int(x) for x in f]

max_element = max([x for x in digits if abs(x) % 100 == 33])

counter = 0
max_sum = 0
for i in rangelen(digits) - 2):
  first, second, third = digits[i], digits[i+1], digits[i+2]

if ((len(str(abs(first))) == 2) + (len(str(abs(second))) == 2) + (len(strabs(third))) == 2)) >= 2 and \ (first + second + third) ** 2 <= max._element:
  counter += 1
  max_sum = max(max_sum, first + second + third)

print(counter, max_sum)

# Ответ: 1858 316

Задания 19–21

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: 

– убрать из кучи 3 камня; 
– убрать из кучи 6 камней; 
– уменьшить количество камней в куче в 3 раза (количество камней, полученное при делении, округляется до меньшего). 

Например, из кучи в 20 камней за один ход можно получить кучу из 17, 14 или 6 камней. Игра завершается, когда количество камней в куче становится не более 25. 

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

В начальный момент в куче было S камней, S≥ 26.

19. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. 

20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: 
– Петя не может выиграть за один ход; 
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. 

Найденные значения запишите в ответе в порядке возрастания.

21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются условия: 
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; 
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

# Решение:

def f(s, k):
    if s <= 25:
        return k % 2 == 0
    if k == 0:
        return 0
    m = [f(s-3, k-1), f(s-6, k-1), f(s//3, k-1)]
    if k % 2 != 0:
        return any(m)
    return all(m)
# решение от t.me/soldaevainfo
print("19:", min([s for s in range(26, 100) if f(s, 2)]))
print("20:", *[s for s in range(26, 100) if (not f(s, 1)) and f(s, 3)][:2])
print("21:", min([s for s in range(26, 100) if (not f(s, 2)) and f(s, 4)]))

# ответы
# 19: 78
# 20: 81 82
# 21: 87

Задание 22

Вариант 1

Определите максимальное количество процессов, которое может быть выполнено за первые 18 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1. Например, для приведённой таблицы пять процессов будут выполнены за первые 6 мс. Это процессы 1, 2, 3, 4, и 6.

Вариант 2

Определите какое максимальное число процессов завершиться за 25 секунд включительно, при условии, что все независимые друг от друга процессы могут выполняться параллельно, а процессы начинаются как можно раньше, нумерация миллисекунд начинается с 1.

Задание 24

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита.

Определите в прилагаемом файле последовательность идущих подряд символов наименьшей длины, в которой комбинация цифр 2025 (в указанном порядке) встречается 60, при этом последовательность начинается на комбинацию цифр 2025, а также содержит не менее 120 букв Y.

В ответе запишите длину найденной последовательности.

# Решение:

s = open("24.txt").readline()

m = 10**3 # ищем минимум
for l in range(len(s)):
    if s[l:l+4] == "2025":
        for r in range(l + m, l, -1):
            p = s[l:r + 1]
# решение от t.me/soldaevainfo
            if p.count("2025") < 60 or p.count("Y") < 120:
                break
            if p.count("2025") == 60 and p.count("Y") >= 120:
                m = min(m, len(p))

print(m)

Задание 25

Вариант 1

Пусть М — сумма минимального и максимального простых делителей числа. Если у числа оказывается меньше двух таких делителей, М считается раным 0. 

Напишите программу, которая перебирает целые числа, большие 7 000 000, в порядке возрастания и ищет среди них такие, для которых значение М оканчивается на 13.

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

# Решение:

def isPrime(n):
    return n > 1 and all(n % d != 0 for d in range(2, int(n**0.5) + 1))

def m(n):
    divs = set()
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            if isPrime(d):
                divs.add(d)
            if isPrime(n // d):
                divs.add(n // d)
    if len(divs) >= 2:
        return min(divs) + max(divs)
    else:
        return 0
# решение от t.me/soldaevainfo
x = 7_000_000 + 1
k = 0
while k < 5:
    if m(x) % 100 == 13:
        print(x, m(x))
        k += 1
    x += 1

# ответ
# 7000018
# 7000076
# 7000088
# 7000096
# 7000124

# Решение:

def isPrime(n):
    return n > 1 and all(n % d != 0 for d in range(2, int(n**0.5) + 1))

def m(n):
    divs = set()
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            if isPrime(d):
                divs.add(d)
            if isPrime(n // d):
                divs.add(n // d)
    if len(divs) >= 2:
        return min(divs) + max(divs)
    else:
        return 0
# решение от t.me/soldaevainfo
x = 6_000_000 + 1
k = 0
while k < 6:
    if m(x) % 100 == 19:
        print(x, m(x))
        k += 1
    x += 1

# ответ
# 6000002 3519
# 6000034 3000019
# 6000176 319
# 6000190 85719
# 6000272 375019
# 6000276 26319

# Решение:

f= open("26.txt")
n = int(f.readline())
plan = []
tors in f:
  start, end = map(int, s.split())
  plan.append ([end, start])
plan.sort()
itog = []
for event in plan:
  if itog == []:
   itog.append(event)
  elif itog[-1][O] < event[1]:
itog.append(event)

for event in plan:
if event[1] > itog[-2][0] and event[1] > itog[-1][1]:
  del itog[-1]
itog.append (event)
print(itog)
print(len(itog), itog[-1][O])  

# Примерный код для вопроса к файлу Б:

clustersB.sort(key = len)
MinMaxClustersB = [clustersB[0], clustersB[-1]]

centersB = [getCenter(c) for c in MinMaxClustersB]
# решение от t.me/soldaevainfo
Q1 = dist(centersB[0], centersB[-1])
Q2 = 0
for p in clustersB[0]:
    d = dist(centersB[0], p)
    Q2 = max(Q2, d)
for p in clustersB[-1]:
    d = dist(centersB[-1], p)
    Q2 = max(Q2, d)

Александра Березина, методист школы insperia