|
№1. ЗАДАЧА «МІЖНАРОДНА КОНФЕРЕНЦІЯ»(100 БАЛІВ)
Вас найняли для того, щоб визначити місця дипломатів за столом обговорень міжнародної конференції. На конференцію запрошено по одному дипломату з N різних країн світу. Кожен дипломат знає від однієї до п'яти мов. Дипломати, які не знають спільної мови, не можуть розмовляти один з одним. До того ж, деякі країни проголосили, що не будуть підтримувати дипломатичних стосунків з деякими іншими, тобто представники цих країн не будуть розмовляти один з одним. Ваше завдання полягає в розробці програми DIPLOMAT.pas/.c/.cpp, що визначає місця за столом для дипломатів таким чином, щоб кожен мав можливість розмовляти з обома своїми сусідами, які сидять ліворуч та праворуч від нього.
Стіл, що використовується, — круглий і розрахований на N персон (N£20). Дипломат може спілкуватися з дипломатом, який сидить ліворуч, однією мовою, а з дипломатом, що сидить праворуч, — іншою.
Технічні вимоги:
Вхідний файл: DIPLOMAT. DAT.
Вихідний файл: DIPLOMAT. SOL.
Програма: diplomat.pas/.c/.cpp
Формат вхідних даних. У першому рядку текстового файла DIPLOMAT. DAT — число N. Далі — N рядків, по одному рядку на дипломата. Кожен рядок — послідовність слів. Сусідні слова відокремлені пробілом. Кожне слово — це послідовність великих латинських літер. Перше слово — код країни — складається з трьох літер. Друге слово має довжину від 1 до 5 літер і являє собою перелік мов, якими може спілкуватися дипломат. Кожна мова позначена однією літерою. Далі — список з не більш ніж N трилітерних слів — кодів країн, з якими уряд дипломата підтримує дипломатичні стосунки.
Формат вихідних даних. До файла DIPLOMAT. SOL треба вивести список дипломатів у порядку розміщення за столом (по одному дипломату в рядку). Кожен рядок складається з трьох слів: перше — код мови, якою дипломат може спілкуватися з сусідом ліворуч, друге — код країни дипломата, третє — код мови для спілкування з сусідом праворуч. Можливе існування кількох розв'язків. Вам потрібно знайти один. Якщо розв'язку не існує, то ваша програма має видати таке повідомлення: «NO SOLUTION EXIST»
Приклад:
|
DIPLOMAT. DAT
|
DIPLOMAT. SOL
|
|
4
USA EC UCR CHN
CHN GC USA GBR
GBR EG UCR CHN
UCR E USA GBR
|
C USA E
E UCR E
E GBR G
G CHN C
|
|
2
USA ER CHN
CHN CP USA
|
NO SOLUTION EXIST
|
Подарунок (uoi2011)
У королівстві Олімпія знаходиться N міст та M двосторонніх доріг, кожна з яких з’єднує рівно два міста. Між двома містами може бути більше однієї дороги. Усі дороги постійно грабуються розбійниками. Останнім часом розбійникам набридло витрачати сили на пограбування і вони звернулися до могутнього і справедливого короля Олімпії з комерційною пропозицією. За цією пропозицією король повинен надіслати розбійникам подарунок, що складається з золотих та срібних монет. У відповідь на люб’язність короля розбійники припинять грабувати певні дороги. Для кожної з доріг встановлена мінімальна кількість золотих і мінімальна кількість срібних монет у подарунку, щоб її пограбування скінчились. Тобто, якщо у подарунку K золотих та L срібних монет, то припиняється пограбування усіх доріг, для яких необхідна кількість золотих монет менша або рівна K, а кількість срібних монет менша або рівна L.
В скарбниці короля немає жодної золотої або срібної монети, але є Олімпійські Тугрики. Ціна однієї золотої монети в тугриках – G, а срібної – S. Король дуже хоче, щоб після відправлення подарунку розбійникам між кожною парою міст існував хоча б один безпечний шлях, який, можливо, проходить через інші міста.
Завдання Напишіть програму gift, яка за даними про міста і дороги у королівстві та цінами монет, знайде мінімальну кількість тугриків, яку потрібно витратити королю для того, щоб отримати безпечні шляхи між кожною парою міст у королівстві.
Вхідні дані Перший рядок вхідного файлу gift.dat містить два цілих числа N і М (2≤N≤200, 1≤М≤50 000) – кількість міст і кількість доріг у королівстві Олімпія. Другий рядок містить числа G і S (1≤G, S≤109). Наступні М рядків містять інформацію про дороги та опис пропозиції розбійників. У і+2-му рядку вхідного файлу розташовано 4 натуральних числа, перші два з яких – номери міст, що з’єднані і-ою дорогою (міста нумеруються від 1 до N), наступні два – мінімальна кількість золотих і мінімальна кількість срібних монет, що треба вислати розбійникам в подарунку, щоб і-ту дорогу припинили грабувати. Обидва числа не перевищують 109.
Вихідні дані Єдиний рядок вихідного файлу gift.sol має містити одне ціле число – мінімальну кількість тугриків, що потрібно витратити королю на купівлю золотих та срібних монет, щоб досягнути своєї мети, або -1, у випадку, якщо жодна кількість тугриків не допоможе.
Оцінювання Щонайменше у 30% тестів N не буде перевищувати 30 та M не буде перевищувати 150. Щонайменше у 70% тестів M не буде перевищувати 4000.
Приклад вхідних та вихідних даних
|
gift.dat
|
gift.sol
|
|
3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1
|
30
|
Пояснення: достатньо покласти у подарунок розбійникам 5 золотих та 20 срібних монет і вони відкриють другу та третю дороги. На купівлю цих монет король витратить 30 тугриків.
Музей (uoi2010)
У столиці країни Олімпія збудований Музей Олімпійської Слави, де виставлено нагороди школярів країни з різних предметних олімпіад. Будівля музею складається з виставкових залів, з’єднаних коридорами. Коридор сполучає рівно два зали. Відомо, що кожного залу музею можна дістатися з будь-якого іншого залу, прямуючи коридорами. Також відомо, що кількість коридорів дорівнює кількості залів.
Вночі музей патрулюється охоронцями. Кількість охоронців дорівнює кількості залів, та у кожен момент часу охоронець доглядає за своїм залом. Кожну годину згідно плану патрулювання деякі з охоронців переходять в іншу залу, а інші залишаються на місті. План патрулювання відповідає таким вимогам:
1. Для кожної зали план задає чи залишиться її охоронець на місці, чи перейде до певної зали, яка сполучена з поточною коридором.
2. Після переходів охоронців, у кожній залі повинен опинитися рівно один охоронець.
3. Кожну годину застосовується один і той самий план патрулювання.
Наприклад, на рисунку наведений один з можливих планів патрулювання. Згідно йому кожну годину охоронець, що знаходиться у залі 1, переходить до залу 2; охоронець з залу 2 – до залу 3; з залу 3 – до залу 1; охоронці з залів 4 та 5 міняються місцями, а охоронець з залу 6 всю ніч проводить у цьому залі.
Завдання Напишіть програму MUSEUM, яка за інформацією про кількість залів музею і їх сполучення коридорами знайде кількість різних планів патрулювання музею за модулем P.
Вхідні дані Перший рядок вхідного файлу MUSEUM.DAT містить пару цілих чисел N (3≤N≤50 000) – кількість залів у музеї, та P (2≤P≤10 000). Наступні N рядків містять пари цілих чисел від 1 до N – номери залів, що з’єднані коридором.
Вихідні дані Єдиний рядок вихідного файлу MUSEUM.SOL має містити ціле число – кількість планів патрулювання музею, за модулем P (остачу від ділення шуканої кількості на P).
Оцінювання Щонайменше в 20% тестів буде виконуватись додаткове обмеження N≤20.
Щонайменше в 60% тестів буде виконуватись додаткове обмеження N≤1000.
Приклад вхідних та вихідних даних
|
MUSEUM.DAT
|
MUSEUM.SOL
|
|
6 1000
1 2
2 3
3 1
3 4
4 5
4 6
|
20
|
Існує 20 різних планів патрулювання: (1, 2, 3, 4, 5, 6), (1, 2, 3, 5, 4, 6), (1, 2, 3, 6, 5, 4), (1, 2, 4, 3, 5, 6), (1, 3, 2, 4, 5, 6), (1, 3, 2, 5, 4, 6), (1, 3, 2, 6, 5, 4), (2, 1, 3, 4, 5, 6), (2, 1, 3, 5, 4, 6), (2, 1, 3, 6, 5, 4), (2, 1, 4, 3, 5, 6), (2, 3, 1, 4, 5, 6), (2, 3, 1, 5, 4, 6), (2, 3, 1, 6, 5, 4), (3, 1, 2, 4, 5, 6), (3, 1, 2, 5, 4, 6), (3, 1, 2, 6, 5, 4), (3, 2, 1, 4, 5, 6), (3, 2, 1, 5, 4, 6), (3, 2, 1, 6, 5, 4). На рисунку з умови зображено план (2, 3, 1, 5, 4, 6).
Торговець (uoi2009)
Торговець володіє трьома видами товарів: алмази, яблука та шовк. Для кожного товару відомо вартість у золотих монетах за одиницю ваги та його кількість у торговця.
В країні, де живе торговець, є N міст, які пронумеровані від 1 до N. Рідне місто торговця має номер 1, а столиця – номер N. Щоб дістатися столиці, де торговець може продати товар, йому потрібно проїхати певним маршрутом через інші міста. Між деякими парами міст існують дороги, проїзд по яким коштує певної кількості золотих. У кожному місті стягується податок за провезення кожного з видів товару, заданий у відсотках від вартості провезеного через місто товару. Відомо, що виїхавши з будь-якого міста, торговець не може до нього повернутися. Будь-які два міста з’єднані не більше ніж однією дорогою.
Задача торговця отримати найбільший прибуток – різницю отриманих у столиці коштів за проданий товар та витрат за подорож до столиці. Він не зобов’язаний брати з собою весь свій товар. Торговець завжди має достатньо золотих для виплати податків, та не може розрахуватися товаром, який він везе до столиці. Усі дороги ведуть лише в одному напрямку.
Завдання
Напишіть програму SALESMAN, що за інформацією про кількість одиниць ваги різних видів товару у торговця, ціни на ці товари у столиці, податки у містах, дороги між містами та вартість проїзду по цих дорогах встановить максимальний прибуток, що може отримати торговець від реалізації товару.
Вхідні дані
Перший рядок вхідного файлу SALESMAN.DAT містить два цілих числа N (2≤N≤500) та M (M³1) – кількість міст та доріг між ними. Другий рядок містить три цілих невід’ємних числа, що відповідають кількостям одиниць ваги алмазів, яблук та шовку, що належать торговцю. Третій рядок містить три цілих невід’ємних числа – вартість одиниці ваги алмазів, яблук та шовку відповідно. Наступні рядки з 4-го по N+1 містять по три цілих числа від 0 до 100 включно, що відповідають відсоткам від вартості алмазів, яблук та шовку, що стягується у відповідно у містах від 2 до N-1 у якості податку. У списку міст не враховані рідне місто торговця 1 та столиця N, як такі, що не стягують податок. Наступні M рядків містять по три цілих невід’ємних числа, перші два з яких від 1 до N задають пару міст, між якими прокладено дорогу, а третє – вартість проїзду цією дорогою. Дороги ведуть в напрямку від міста, яке вказано першим, до того, яке вказано другим. Кількості одиниць ваги кожного з видів товару у торговця, вартості товарів та ціни проїзду по дорогам не перевищують 100.
Вихідні дані
Єдиний рядок вихідного файлу SALESMAN.SOL має містити одне число – точне значення знайденого максимального прибутку від поїздки до столиці. Відповідь завжди повинна містити рівно два знаки після крапки. У випадках коли торговець не може отримати прибутку чи дістатися столиці існуючими дорогами, потрібно вивести 0.00
Приклад вхідних та вихідних даних
|
SALESMAN.DAT
|
SALESMAN.SOL
|
|
4 4
10 5 20
100 5 12
15 40 25
90 20 10
1 2 5
1 3 10
3 4 10
2 4 15
|
1025.00
|
|
