Решение задачи Слух с Codeforces
Без пояснения   Просмотров: 118
Вова пообещал себе больше никогда не играть в игры... Но недавно компания Firestorm выпустила очень популярную игру — World of Farcraft, и Вова, конечно же, начал в неё играть.
Он впал в ступор при выполнении очередного квеста — необходимо было прийти в поселение Надгород и распространить там слух.
Вова знает, что в Надгороде живут n персонажей. Некоторые персонажи дружат между собой и готовы делиться информацией друг с другом. Также он знает, что i-й персонаж готов начать распространять слух за c i золота. Как только персонаж узнаёт слух, он рассказывает его всем своим друзьям, которые, в свою очередь, тоже начинают распространять этот слух (но уже бесплатно).
Вова хочет, чтобы слух узнали все n персонажей Надгорода. За какое минимальное количество золота он сможет это сделать?
Посмотрите примечание для лучшего понимания задачи.
Он впал в ступор при выполнении очередного квеста — необходимо было прийти в поселение Надгород и распространить там слух.
Вова знает, что в Надгороде живут n персонажей. Некоторые персонажи дружат между собой и готовы делиться информацией друг с другом. Также он знает, что i-й персонаж готов начать распространять слух за c i золота. Как только персонаж узнаёт слух, он рассказывает его всем своим друзьям, которые, в свою очередь, тоже начинают распространять этот слух (но уже бесплатно).
Вова хочет, чтобы слух узнали все n персонажей Надгорода. За какое минимальное количество золота он сможет это сделать?
Посмотрите примечание для лучшего понимания задачи.