Условие

Вы — менеджер по развитию компании «ТриФазаСбыт», которому поручили вести расширение влияния на другие регионы. Достигается это через покупку контрактов на их снабжение.

Стратегическая ценность («полезность») каждого региона меняется в зависимости от того, кто владеет соседними территориями. Если регион граничит с вашими землями, его ценность растет на единицу. Если с землями конкурентов — падает на единицу. Базовое значение для каждого региона одинаково и равно единице.

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

Формат входных данных

Первая строка содержит одно целое число — B, ваш бюджет на торги. Вторая строка содержит одно целое число — N, общее количество регионов на карте.

Далее следуют N строк, каждая из которых описывает регион под номером от 1 до N. Через пробел приводятся: номер владельца, цена контракта, далее произвольное число номеров соседних регионов. Гарантируется, что соседство регионов согласовано.

Владелец:
             - 0 – регион на продаже.
             - 1 – регион находится в вашем распоряжении
             - иные значения – регионы конкурентов

Формат выходных данных

Произвольное количество выкупаемых номеров регионов через пробел.

Если вы принимаете решение не покупать ни одного региона, выведите одно слово `End` или пустую строку.

Для решения этой задачи у вашей команды есть 20 попыток.

Видео-разбор

 

Разбор

Ценность каждого региона в задаче зависит от окружающих его территорий. Каждому региону присваивается базовое значение в единицу. За каждого соседа, принадлежащего тому же владельцу, ценность растёт на единицу, а за каждого соседа конкурента - падает.

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

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

При нуловой или отрицательной ценности регионов, не стоит их покупать.

Последнее изменение: пятница, 15 мая 2026, 04:38