Помогите сплетникам как можно эффективнее распространить слухи
Нужно найти алгоритм, который поможет n сплетникам распространить слухи за минимальное количество сообщений.
5К открытий5К показов
n сплетников знают слухи, каждый знает о чём-то своём. Они хотят поделиться друг с другом слухами через сообщения. Тот, кто отправляет сообщение, включает в него все слухи, которые слышал, но сообщение может иметь только одного адресата.
Какое минимальное количество сообщений им понадобится, чтобы каждый узнал все слухи?
Ответ
Минимальное количество сообщений — 2n – 2.
Почему?
Есть несколько способов решить эту задачу. Например, можно определить одного человека — назовём его Сплетник 1 — которому все остальные отправят свои слухи. После того, как Сплетник 1 узнает все слухи, он запишет их в сообщение, добавит свой слух и разошлёт это сообщение каждому из n – 1 участников.
2n – 2 — минимальное количество сообщений, потому что если увеличить количество участников на 1, потребуется как минимум 2 дополнительных сообщения — к этом сплетнику и от него, что и демонстрирует алгоритм.
5К открытий5К показов
Попросили ChatGPT и Yandex GPT придумать несколько задач, которые зайдут программистам. Сумеете решить?
Собрали несколько математических задач высокого уровня сложности и добавили варианты решения на Python.
История о том, как я решил 600 задач на Leetcode и прошел несколько coding сессий в таких компаниях как Booking, Careem и Avito.
Математика и компьютерные науки идут рука об руку. Подобрали 7 математических формул разного уровня сложности для проверки — сможете ли вы их реализовать? И на всякий случай снабдили статью нашими решениями.