⤵️ Продолжение шпаргалки по #ЕГЭ27 #useful

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

Расстояние между двумя точками на плоскости между точками A(x1, y1) и B(x2, y2) вычисляется по формуле: d(A,B)= ((x2 - x1)**2 + (y2 - y1)**2)**0.5

Что можно описать функцией:

def d(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x2 - x1)**2 + (y2 - y1)**2)**0.5

print(d([0, 0], [3, 4]))  # 5.0

Но так же надо заметить, что эта функция уже описана в питоне, а именно в библиотеке math.

Тот же самый код, но короче через math:

from math import dist

print(dist([0, 0], [3, 4]))

#⃣ Полный список разборов в одном месте
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

⤵ Продолжение шпаргалки по #ЕГЭ27 #useful

Теперь разберём функцию для поиска центра кластера. Для примера возьмём кластер:
[[0, 0], [4, 3], [2, 2], [5, 6]]

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

Алгоритм следующий:
- Берём произвольную точку p из кластера.
- Вычисляем сумму расстояний от p до всех других точек g этого кластера.
- Повторяем для всех точек и выбираем ту, у которой сумма минимальна.

👩‍💻 Код программы:

from math import dist

def center(cl):
    R = []
    for p in cl:
        summa = 0
        for g in cl:
            summa += dist(p, g)
        R.append([summa,p])
    return min(R)[1]


clustersA = [[[0, 0], [4, 3], [2, 2], [5, 6]], []]
cl = clustersA[0]

print(center(cl))  # [2, 2] - центр первого кластера из двух

Суммы для всех точек:

15.638676800652844 [0, 0]
10.39834563766817 [4, 3]
10.06449510224598 [2, 2]
15.972527336075034 [5, 6]

👩‍💻 Комментарии к коду:

1⃣ from math import dist

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

2⃣ def center(cl):

Функция, которая находит "центр" кластера (точку с минимальной суммой расстояний до остальных).

3⃣ R = []

Список для сохранения результатов.

4⃣ for p in cl:

Первый цикл – перебирает каждую точку кластера.

5⃣ summa = 0

Обнуление суммы расстояний для текущей точки p.

6⃣ for g in cl:

Вложенный цикл – вычисляет расстояние от p до всех точек g в кластере.

7⃣ summa += dist(p, g)

Накопление суммы расстояний для каждой точки p

8⃣ R.append([summa, p])

Cохранение суммы и точки p в список R.

0⃣ return min(R)[1]

Поиск точки с минимальной суммой расстояний (центр).

1⃣1⃣ clustersA = [[[0, 0], [4, 3], [2, 2], [5, 6]], []]

Тестовые данные: список из двух кластеров (второй пуст).

1⃣2⃣ cl = clustersA[0]

Выбор первого кластера для обработки.

1⃣3⃣ print(center(cl))

Вывод результата работы функции.

#⃣ Полный список разборов в одном месте
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

⤵ Продолжение шпаргалки по #ЕГЭ27 #useful

Кульминация решения (опять же на примере кластеров из файла B) - поиск центров кластеров и вычисление среднего арифметическое абсцисс центров кластеров файла B и среднего арифметическое ординат центров кластеров файла B.

👩‍💻 Код программы:

centersB = [center(cl) for cl in clustersB]
pxB = sum(x for x, y in centersB) / 3 * 10000
pyB = sum(y for x, y in centersB) / 3 * 10000
print(int(pxB), int(pyB))

👩‍💻 Комментарии к коду:

1⃣ centersB = [center(cl) for cl in clustersB]

Находим центры каждого кластера из списка clustersB

2⃣ pxB = sum(x for x, y in centersB) / 3 * 10000

Вычисляем среднюю x-координату центров кластеров, умножаем на 10000 и делим на 3 (масштабирование)

3⃣ pyB = sum(y for x, y in centersB) / 3 * 10000

Вычисляем среднюю y-координату центров кластеров, умножаем на 10000 и делим на 3 (масштабирование)

4⃣ print(int(pxB), int(pyB))

Выводим результат в виде целых чисел

#⃣ Полный список разборов в одном месте
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

Ребят, если найдёте интересные задачки с ДВ — кидайте их мне в лс @ilandroxxy или в анонимные сообщения канала (новая функция в Телеграме, можно отправить по кнопке с картинкой). Всем завтра удачи! Ни пуха ни пера! 💪🔥

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ11 по информатике

🚩 Условие задачи:

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

Известно, что для хранения 703_569 серийных номеров доступно не более 77 Мбайт памяти.
Определите максимально возможную мощность алфавита, используемого для записи серийных номеров.

👩‍💻 Код решения:

sym = 246
byte = 77 * 2 ** 20 / 703_569
#  не более 77 Мбайт - поэтому округляем вниз
print(byte)  # 114.758 -> 114
bit = 114 * 8

#  не более 77 Мбайт - поэтому округляем вниз
print(bit / sym)  # 3.707 -> 3

# Максимальная мощность:
print(2 ** 3)  # 8

# Ответ: 8

🚩 Условие задачи 2:

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

Известно, что для хранения 2984523 серийных номеров доступно не менее 14 Мбайт памяти.
Определите минимально возможную мощность алфавита, используемого для записи серийных номеров.

👩‍💻 Код решения:

from math import *

for k in range(1, 10000):
    bit = ceil(log2(kod))
    byte = ceil(3410 * bit / 8)
    if 2_984_523 * byte >= 14 * 1024 * 1024:
        print(kod)
        break

# Ответ: 2

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩 Разбор #ДВ2025 номера #ЕГЭ9 по информатике

🚩 Условие задачи:

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

👩‍💻 Код решения:

A = []
for s in open('9.csv'):
    M = [int(x) for x in s.split(';')]
    p3 = [i for i in M if M.count(i) == 3]
    np = [i for i in M if M.count(i) == 1]
    if len(p3) == 3 and len(np) == 3:
        if p3[0] < 2 * min(np):
            A.append(sum(M))
print(sum(A) // len(A))

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ13 по информатике

🚩 Условие задачи:

Адрес сети и широковещательный адрес не могут быть использованы для адресации сетевых устройств.

Сеть задана ІР-адресом одного из входящих в неё узлов 97.191.34.206 и сетевой маской 255.255.255.240. Определите наибольший IP-адрес данной сети, который может быть присвоен компьютеру.

👩‍💻 Код решения:

from ipaddress import *
net = ip_network('97.191.34.206/255.255.255.240', 0)
for ip in net:
    print(ip)  # 97.191.34.206
    # 97.191.34.207 - не учитываем так как широковещательный

#Ответ: 9719134206

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩 Разбор #ДВ2025 номера #ЕГЭ8 по информатике

🚩 Условие задачи:

Даны 9 буквы слова КОМПЬЮТЕР в алфавитном порядке и нужно найти код с нечетным номером, который не начинается на гласные буквы и содержит одну букву К.

👩‍💻 Код решения:

from itertools import *
n = 0
for p in product(sorted('КОМПЬЮТЕР'), repeat=6):
    n += 1
    word = ''.join(p)
    if word[0] not in 'ОЮЕ':
        if word.count('К') == 1:
            if n % 2 != 0:
                print(n)

# Ответ: 472385

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩 Разбор #ДВ2025 номера #ЕГЭ5 по информатике

🚩 Условие задачи:

На вход алгоритма подаётся натуральное число N.
Алгоритм строит по нему новое число R следующим образом.
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописывается справа две последние цифры троичной записи;
б) если число N не делится на 3, то остаток от деления умножается на 5, переводится в троичную запись и дописывается в конец числа.
3. Результат переводится в десятичную систему и выводится на экран.

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

👩‍💻 Код решения:

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

for n in range(1, 1000):
    s = tri(n)
    if n % 3 == 0:
        s += s[-2:]
    else:
        s += tri(n % 3 * 5)
    r = int(s, 3)
    if r >= 290:
        print(n)
        break

# Ответ: 11

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ24 по информатике

🚩 Условие задачи:

Определите в прилагаемом файле последовательность идущих подряд символов наибольшей длины, в которой символ D встречается 1 раз и он находится в начале, а также содержится 50 цифр. В ответе запишите длину найдённой последовательности.

👩‍💻 Код решения:

f = open('24.txt').readline()
for i in '0123456789':
    f = f.replace(i, '1')
f = f.split('D')
M = [len(x) for x in f if x.count('1') == 50]
print(max(M)+1)

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩 Разбор #ДВ2025 номера #ЕГЭ8 по информатике

🚩 Условие задачи:

Все пятибуквенные слова, составленные из букв В, Е, Н, Е, Р, А записаны в алфавитном порядке и пронумерованы.

Под каким нечетным номером в списке стоит последнее слово, которое не начинается с буквы Н и содержит ровно две буквы В?

👩‍💻 Код решения:

from itertools import *

k = 0
alph = sorted('ВЕНЕРА')
A = product(alph, repeat=5)
for i in A:
    i = ''.join(i)
    k += 1
    if i[0] != 'Н' and i.count('В') == 2 and k % 2 != 0:
        print(k)

# Ответ: 7607

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ14 по информатике

🚩 Условие задачи:

Операнды арифметического выражения записаны в системе счисления с основанием 27: 2107x792_27 + 565х211_27

В записи чисел переменной х обозначена неизвестная цифра из алфавита 27-ричной системы счисления.

Определите наименьшее значение х, при котором значение данного арифметического выражения кратно 26.
Для найденного х вычислите частное от деления значения арифметического выражения на 26 и укажите его в ответе в десятичной системе счисления.

👩‍💻 Код решения:

for x in '0123456789ABCDEFGHIJKLMNOPQ':
    a = int(f'2107{x}792', 27) + int(f'565{x}211', 27)
    if a % 26 == 0:
        print(a // 26)
        break

#Ответ: 897607140

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ17 по информатике

🚩 Условие задачи:

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

👩‍💻 Код решения:

f = open('17.txt').readline()
M = [int(i) for i in f]
max_19 = max(i for i in M if abs(i) % 100 == 19)

A = []
for i in range(len(M) - 1):
    if (len(str(abs(M[i]))) == 2) + (len(str(abs(M[i+1]))) == 2) == 1:
        if M[i] + M[i+1] > max_19:
            A.append(M[i] + M[i+1])
print(len(A), max(A))

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩🚩🚩🚩 Разбор #ДВ2025 номера #ЕГЭ19-21 по информатике

🚩 Условие задачи:

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

Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней. В начальный момент в куче было S камней, S ≥ 20.

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

👩‍💻 Код решения:

from math import ceil, floor
def F(s, n):
    if s <= 19:
        return n % 2 == 0
    if n == 0:
        return 0
    h = [F(s-7, n-1), F(floor(s/3), n-1)]
    return any(h) if (n - 1) % 2 == 0 else all(h)

print([s for s in range(20, 1000) if F(s, 2)])
print([s for s in range(20, 1000) if F(s, 3) and not F(s, 1)])
print([s for s in range(20, 1000) if F(s, 4) and not F(s, 2)])

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ15 по информатике

🚩 Условие задачи:

Укажите наименьшее целое значение А, при котором выражение
(2y + 3x < A) V (x > 15) V (y > 35)
истинно для любых целых положительных значений х и у.

👩‍💻 Код решения:

def F(x, y, A):
    return (2 * y + 3 * x < A) or (x > 15) or (y > 35)

for A in range(1, 1000):
    if all(F(x, y, A) for x in range(1, 1000) for y in range(1, 1000)):
        print(A)
        break

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ12 по информатике

🚩 Условие задачи:

Дана программа для Редактора:
ПОКА нашлось (577) ИЛИ нашлось (677) ИЛИ нашлось (657)
ЕСЛИ нашлось (577)
ТО заменить (577,76)

ЕСЛИ нашлось (677)
ТО заменить (677,75)

ЕСЛИ нашлось (657)
ТО заменить (657, 56)

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

👩‍💻 Код решения:

for n in range(4, 10000):
    s = '5' + n * '7'
    while '577' in s or '677' in s or '657' in s:
        if '577' in s:
            s = s.replace('577', '76', 1)
        if '677' in s:
            s = s.replace('677', '75', 1)
        if '657' in s:
            s = s.replace('657', '56', 1)
    summ = sum([int(i) for i in s])
    if summ == 76:
        print(n)

# Ответ: 19

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

🚩🚩 Разбор #ДВ2025 номера #ЕГЭ25 по информатике

🚩 Условие задачи:

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

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

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

👩‍💻 Код решения:

def divisors(x):
    div = []
    for j in range(2, int(x**0.5)+1):
        if x % j == 0:
            div += [j, x // j]
    return sorted(set(div))

def Prost(x):
    if x == 1:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

cnt = 0
for x in range(2_900_000, 10**10):
    div = divisors(x)
    if len(div) == 2 and Prost(div[0]) and Prost(div[1]):
        if str(div[0]).count('0') == 1 and str(div[1]).count('0') == 1:
            print(x, max(div))
            cnt += 1
            if cnt == 5:
                break

#⃣ Разбор задач ДВ, первый день 10.06.25
#⃣ Шпаргалки по всем остальным номерам ЕГЭ

➡Информатика ЕГЭ | чатик itpy 🧑‍💻

👨‍💻 Разбор задач ДВ, первый день 10.06.25

#⃣ Вся теория для ЕГЭ в одном месте
#⃣ Полный список разборов в одном месте
#⃣ Шпаргалки по всем остальным номерам ЕГЭ