Задача NewFerry
Група бізнесменів вирішила поєднати ділові переговори з
екстремальними розвагами у дикому лісі. Запросили
фахівців з організації подібних заходів, ті принесли
сценарій, частину якого запозичили з задачі
Ferry -
переправу групи річкою на надувному човні на дві особи
за мінімальний час. Для кожного бізнесмена відомий час,
за який він може переправитися на човні; якщо у човні
перебувають 2 бізнесмени, час переправи дорівнює часу
менш розторопного з них. Але героям задачі Ferry було
легко! Вони на час переправи забули про все, крім того,
що потрібно переправитися якомога швидше. А для
бізнесменів дуже суттєво, щоб протягом хоча б деякого
часу ніхто з них не проводив змов (особистих сепаратних
переговорів з метою нажитися за рахунок решти колег). З
цієї причини, деякі пари бізнесменів ніяк не можна
залишати без нагляду конкурентів — ні у човні, ні на
якомусь із берегів. За який мінімальний час всі вони
зможуть переправитися, якщо головне — гарантувати
відсутність змов, а вже у другу чергу слід мінімізувати
час?
Технічні умови. Програма читає з клавіатури загальну
кількість бізнесменів N (4<=N<=12); потім N натуральних
чисел — час, необхідний кожному з них на переправу;
потім вказується число M — кількість тих пар, які можуть
проводити сепаратні переговори; потім йдуть M описів
наступного формату. Перші два числа кожного опису
вказують тих двох бізнесменів, які можуть наважитися на
змову; далі йде кількість та перелік конкурентів
(присутність хоча б одного з конкурентів гарантує, що
змова не відбудеться). Оскільки у бізнесменів нема
друзів і ворогів, а є лише ділові інтереси, не виключена
ситуація, коли одна й та сама пара бізнесменів
виявляється і потенційними змовниками, і конкурентами,
які слідкують один за одним, щоб не допустити інших
змов. Всі дані вводяться однією стрічкою через пропуски.
Програма виводить на екран -1 якщо бізнесменам так і не
вдасться переправитися через річку, інакше — знайдений
мінімальний час (він гарантовано не перевищує
2000000000).
Приклад
Введення
4 7 3 2 5 2 1 2 1 4 2 3 2 1 4
Виведення
24
Задача NewFerry
Группа бизнесменов решила объединить деловые переговоры
с экстремальными развлечениями в диком лесу. Пригласили
специалистов по организации подобных мероприятий, те
принесли сценарий, часть которого позаимствовали из
задачи Ferry - переправу группы через речку на надувной
лодке на два человека за минимальное время. Для каждого
бизнесмена известно время, за которое он может
переправиться на лодке; если в лодке находятся
2
бизнесмена, время переправы равно времени менее
расторопного из них. Но героям задачи Ferry было легко!
Они на время переправы забыли обо всем, кроме того, что
необходимо переправиться как можно быстрее. А для
бизнесменов очень важно, чтобы даже в небольшой
промежуток времени никто из них не сговорился (не
проводил личных сепаратных переговоров с целью нажиться
за счет остальных коллег). По этой причине некоторые
пары бизнесменов никак нельзя оставлять без присмотра
конкурентов — ни в лодке, ни на любом берегу. За какое
минимальное время все они смогут переправиться, если
главное — гарантировать отсутствие сговора, а во вторую
очередь следует минимизировать время?
Технические условия. Программа читает с клавиатуры общее
количество бизнесменов N (4<=N<=12); затем N натуральных
чисел — время, необходимое каждому из них на переправу;
затем указывается число M — количество тех пар, которые
могут проводить сепаратные переговоры; затем идут M
описаний следующего формата. Первые два числа каждого
описания указывают тех двух бизнесменов, которые могут
решиться на сговор; далее идет количество и перечисление
конкурентов (присутствие хотя бы одного из конкурентов
гарантирует, что сговор не состоится). Поскольку у
бизнесменов нет друзей и врагов, а есть только деловые
интересы, не исключена ситуация, когда одна и та же пара
бизнесменов является и потенциальными заговорщиками, и
конкурентами, которые следят друг за другом, чтобы не
допустить других сговоров. Все данные вводятся одной
строкой через пробелы. Программа выводит на экран
-1,
если бизнесменам так и не удалось переправиться через
речку, иначе — найденное минимальное время (оно
гарантированно не превосходит 2000000000).
Пример
Ввод
4 7 3 2 5 2 1 2 1 4 2 3 2 1 4
Вывод
24
|
