Условие

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Last modified: Wednesday, 4 February 2026, 9:30 AM