Нора крота представляет собой 1000 комнат, пронумерованных номерами от 1 до 1000. Между некоторыми комнатами крот прорыл проходы так, что из любой комнаты можно попасть в любую другую. В первой норе было x₁ орехов, во второй - x₂ орехов, ... , в 1000-ой норе было x₁₀₀₀ орехов. Однажды крот решил по-новому разложить орехи. Крот хочет, чтобы в первой норе оказалось y₁ орехов, во второй - y₂ орехов, ... , в 1000-ой норе - y₁₀₀₀ орехов. За одну операцию крот может перенести из одной норы в другую сколько угодно (если хватает) орехов, если эти две норы непосредственно соединены проходом. За какое наименьшее число операций крот гарантированно сможет осуществить своё желание для любого расположения проходов?
Нора крота представляет собой 1000 комнат, пронумерованных номерами от 1 до 1000. Между некоторыми комнатами крот прорыл проходы так, что из любой комнаты можно попасть в любую другую. В первой норе было x₁ орехов, во второй - x₂ орехов, ... , в 1000-ой норе было x₁₀₀₀ орехов. Однажды крот решил по-новому разложить орехи. Крот хочет, чтобы в первой норе оказалось y₁ орехов, во второй - y₂ орехов, ... , в 1000-ой норе - y₁₀₀₀ орехов. За одну операцию крот может перенести из одной норы в другую сколько угодно (если хватает) орехов, если эти две норы непосредственно соединены проходом. За какое наименьшее число операций крот гарантированно сможет осуществить своё желание для любого расположения проходов?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для достижения желаемого распределения орехов кроту необходимо равномерно распределить орехи между всеми норами. Поэтому кроту потребуется 999 операций, чтобы перенести орехи из 1000-ой норы в каждую из первых 999 нор, чтобы в каждой норе оказалось по y₁ ореха. После этого ему придется сделать еще 998 операций, чтобы перенести из 999-ой норы в каждую из первых 998 нор ровно по y₂ ореха, и так далее.
В общем случае, кроту потребуется сделать 999+998+...+1 = 499500 операций, чтобы достичь желаемого распределения орехов во всех норах.