Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Бюро путешествий

(Время: 3 сек. Память: 32 Мб Сложность: 80%)

Далеко не все в Тентуре имеют право носить малиновые штаны, и конечно, не все владеют пепелацем с гравицапой, поэтому для большинства жителей проблема перемещения между планетами была неразрешимой. Но с некоторых пор один предприимчивый чатланин с планеты Плюк вышел на рынок пассажирских перевозок, и за немного чатлов, готов перевозить желающих с планеты на планету. Рейс начинается с планеты Плюк, включает нескольких других планет, и завершается там же, на планете Плюк. Однако при подготовке рейса возникли неожиданные проблемы. Например, если чатланин с планеты Плюк хочет попасть на планету, которая является в рейсе предпоследней – ему невольно придётся посетить все планеты, которые находятся в рейсе между планетой Плюк и его точкой назначения. Очевидно, что часть планет в этом списке могут оказаться пацакскими. Но каждый чатланин обязан носить цак на пацакской планете и, наоборот, каждый пацак должен носить цак на чатланской планете. (Цак — колокольчик для носа, знак отличия для относительно низшей касты на данной планете). А процедура ношения цака унизительна во всех смыслах этого слова…

Поскольку данное бюро путешествий пока не имеет представительств на других планетах, перевозка осуществляется только с планеты Плюк на какую-либо другую, либо с другой планеты на Плюк. Задача планирования рейса упрощается – можно посещать планеты в произвольном порядке (но нельзя посещать одну и ту же планету дважды – в пути может закончиться луц). Необходимо вычислить такой порядок посещения планет, при котором надевать цак на промежуточных планетах придётся минимальное количество раз.

Входные данные

Первая строка входного файла INPUT.TXT содержит натуральное число N ≤ 22 – количество планет, обслуживаемых данным рейсом (не считая планеты Плюк). N следующих строк содержат информацию о планетах, в следующем виде: тип планеты (английская заглавная буква С – чатланская, P – пацакская), количество чатлан, следующих до этой планеты с Плюка, количество пацаков, следующих до этой планеты с Плюка, количество чатлан, с данной планеты на Плюк, количество пацаков, с данной планеты на Плюк. Всего пассажиров ≤ 1000.

Выходные данные

В выходной файл OUTPUT.TXT выводится, сколько раз придётся надевать цак при оптимальном маршруте, затем порядок посещения планет через пробел. Планеты, перечисленные во входном файле, нумеруются начиная с единицы, планета Плюк имеет номер ноль и всегда указывается в последовательности дважды – в начале и в конце последовательности. Если существуют несколько оптимальных маршрутов – то следует выбрать тот, где планета с меньшим номером посещается раньше.

Примеры

INPUT.TXTOUTPUT.TXT
12
C 1 4 5 2
P 2 5 1 4
5 0 2 1 0
24
C 3 0 0 0
C 3 0 0 1
C 3 0 0 1
C 3 0 0 1
3 0 1 2 3 4 0

Пояснение

В первом тесте возможны два варианта маршрута: 0 1 2 0, и 0 2 1 0. В первом варианте при посадке на чатланской планете 1 пятерым пацакам, которые следуют транзитом к своей планете 2, придётся надеть цак, а при следующей посадке на пацакской планете 2, пятерым чатланинам, которые сели на планете 1 и следуют до Плюка, также придётся надеть цак. Итого в первом варианте маршрута цак надевается 10 раз. В варианте 2 цак на промежуточных посадках надевается 4 и 1 раз соответственно, всего 5 раз. Второй вариант предпочтительнее.

Во втором тесте все планеты чатланские, поэтому надевать цак придётся только пацакам. С Плюка пацаки не отправляются, но прибывают с трёх разных планет по одному. Первой посещается единственная планета, где пацак не заходит в пепелац, затем следуют три планеты с одинаковым набором пассажиров – на втором шаге из трёх оставшихся равноценных планет выбирается планета номер 2 как имеющая наименьший номер, затем 3 и оставшаяся 4. Пассажир с последней планеты не имеет промежуточных посадок, с предпоследней совершает одну посадку и надевает цак 1 раз, и оставшийся пассажир надевает цак на двух промежуточных остановках, итого цак надевается 3 раза.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483