`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Задача 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

© LIKT 1998-2024