ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Data Structures > задача:


50692 - How much money?

Гость
• Вопросы к жюри (1)

Задачи сборника

• 50830 - Sorting BST Nodes
• 50803 - Sum of the depths in BST
• 50805 - Sum of the weights in a BST
• 50712 - Moon algebra
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50679 - Jetpack Hurdle Jumping
• 50717 - Hurdle Jumping
• 50692 - How much money?
• 50431 - Sultan's Game
• 50429 - Secret Message
• 50818 - Depth Limited BST
• 50386 - Conformity
• 50790 - Fire Alarm
• 50710 - Permutations
• 50709 - k-ary Strings
• 50708 - Binary Strings

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Prepared by : Sidrit Reka.

How much money?

Question:
Recently there have been a lot of words related to the corruption of soccer federations like FIFA and UEFA. Some of the events that leaded to these accusations were the decisions related to the World Cup 2022 in Qatar and the match Serbia vs. Albania that was a part of the Euro 2016 qualifiers. We tried to investigate a bit more about this case and finally we understood how the scheme of corruption is formed.

The corruption is shown as a set of connections that exist between individuals that know each other. If two persons A and B know each other, A can corrupt B by giving to B 100 $ and also B can corrupt A by giving to A 100 $. Let us say that there is another person C which knows person B and there is another person D which does not know anyone. Now, A can corrupt also C but he needs to pay 200 $ this time, because he can make this corruption only by paying 100 $ to B and then another 100 $ passed to C through B. If A would know C directly, he would have spent only 100 $. In this example, person D cannot corrupt anyone and cannot be corrupted since he does not know anyone else.

Input specification
You will be first given a number (n) which is the number of individuals that work in these federations where 2 <= n <= 100. Then, you will be given n strings which are the names of these individuals. After that, you will be given a number (m), where 0 <= m <= 50, which shows the number of pairs of persons that know each other, followed by (m) pairs of strings that represent these persons.In the end, you will be given 2 names, A and B, meaning that person A wants to corrupt person B.

Output specification
Print as an output the minimum amount of money that person A has to give in order to corrupt person B or print 'Impossible' if B cannot be corrupted by A.

 Sample Input I     Sample Output I   
4
Blatter
Platini
Atkinson
Karadzic
3
Platini Blatter
Atkinson Platini
Karadzic Atkinson
Karadzic Blatter
300
 Sample Input II     Sample Output II   
4
Blatter
Platini
Atkinson
Karadzic
2
Platini Blatter
Karadzic Atkinson
Karadzic Blatter
Impossible


Для отправки решений необходимо выполнить вход.

www.contester.ru