Считаем рёбра
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Имеется три кучи камней. Сизиф таскает по одному камню из кучи в кучу. За каждое перетаскивание он получает от Зевса количество монет, равное разности числа камней в куче, в которую он кладет камень, и числа камней в куче, из которой он берет камень. Сам перетаскиваемый камень при этом не учитывается. Если указанная разность отрицательна, то Сизиф возвращает Зевсу соответствующую сумму. Если Сизиф не может расплатиться, то Зевс позволяет ему перетаскивать в долг. В некоторый момент оказалось, что в каждой куче содержится то же число камней, что и изначально. Каков наибольший возможный заработок Сизифа на этот момент?
Подсказка 1
Попробуем ввести какой-нибудь граф. В качестве вершин хочется брать камни. Что тогда может стать рёбрами?
Подсказка 2
Давайте проводить ребро между двумя камнями, если они лежат в одной куче. Тогда при повторении количеств камней в кучах в графе будет столько же рёбер. Осталось найти связь между числом рёбер и заработком Сизифа.
Введем вспомогательный граф, вершинами которого будут камни, а ребро проводится, если вершины-камни лежат в одной куче. Посмотрим, как изменяется этот граф за одно перетаскивание.
Если мы берем камень из кучи, в которой было 
камней, и добавляем в кучу, где было 
камней, то добавляется 
ребер, а
вычитается 
ребро. Таким образом, количество ребер изменяется на 
Но это как раз равно заработку Сизифа. Поэтому
изменение количества ребер во вспомогательном графе равно заработку Сизифа. Так как по условию повторилась ситуация, в которой в
каждой куче содержится то же число камней, что и изначально, то количество ребер во вспомогательном графе после всех проведенных
операций не изменилось. Значит, заработок Сизифа равен 
монет
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
