| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10973 | Compound Words |
|
| 11017 | Friends |
|
| 11019 | The Gossipy Gossipers Gossip Gossips |
|
| 11080 | Commandos |
|
Description
You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words. Each word will be no longer than 30.
Output
Your output should contain all the compound words, one per line, in alphabetical order.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There is a town with N citizens. It is known that some pairs of people are friends. According to the famous saying that "The friends of my friends are my friends, too" it follows that if A and B are friends and B and C are friends then A and C are friends, too.
Input
Input consists of several datasets. The first line of the input consists of a line with the number T (≤ 20) of test cases to follow.
The first line of each dataset contains two numbers N and M, where N is the number of town’s citizens (1 ≤ N ≤ 30000) and M is the number of pairs of people (0 ≤ M ≤ 500000), which are known to be friends. Each of the following M lines consists of two integers A and B (1 ≤ A ≤ N, 1 ≤ B ≤ N, A ≠ B) which describe that A and B are friends. There could be repetitions among the given pairs.
Output
The output for each test case should contain (on a line by itself) one number denoting how many people there are in the largest group of friends on a line by itself.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Gossiping mechanism is quite simple, but effective. Everything starts with a master gossiper (most probably a she), who hears, witnesses, or makes up some extraordinary news. Whenever she meets another person, she tells him the news. As soon as these people meet others, they tell them the news. Soon, everybody is informed of the news, and the process finishes. Gossipers meet each other daily at the same hours. We have information on when every pair of gossipers meet. For simplicity, days are divided into 100 instants. The first day goes from 0 to 99, the second from 100 to 199, and so on. Suppose the gossiping process starts at time 0. When will it finish? That is, when will all the people be informed of the news?
Input
The first line of the input contains an integer N (≤ 40), indicating the number of test cases.
For each test case, the first line contains two integers M and K. M indicates the number of people in this case (numbered from 1 to M). The master gossiper is always number 1. K indicates the number of pairs of people who meet.
Next, we have 2K lines (two lines for each pair of people who meet). The first line of each pair contains three integers, G1, G2 and V. This line means that gossipers G1 and G2 meet V times a day. The second line contains V numbers from 1 to 99, which indicate the instants when G1 and G2 meet daily.
For example, the pair:
3 7 2
28 88
means: person 3 and person 7 meet twice a day, at instants 28 and 88 everyday (that is, at 28, 88, 128, 188, 228, 288, ...).
You can assume that M ≤ 20, K ≤ M * M, and V ≤ 12. Also, any (G1, G2) pair appears at most once in each test case.
Output
For each test case, the output should consist of a single integer F in one line, indicating the instant when the process finishes. If the process does not finish (for example, there is some isolated person who will never be informed), the result should be ‘−1’.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A group of commandos were assigned a critical task.
They are to destroy an enemy head quarter. The enemy head quarter consists of several buildings and the buildings are connected by roads. The commandos must visit each building and place a bomb at the base of each building. They start their mission at the base of a particular building and from there they disseminate to reach each building. The commandos must use the available roads to travel between buildings. Any of them can visit one building after another, but they must all gather at a common place when their task is done.
In this problem, you will be given the description of different enemy headquarters. Your job is to determine the minimum time needed to complete the mission. Each commando takes exactly one unit of time to move between buildings.
You may assume that the time required to place a bomb is negligible. Each commando can carry unlimited number of bombs and there is an unlimited supply of commando troops for the mission.
Input
The first line of input contains a number T ≤ 100, where T denotes the number of test cases.
Each case describes one head quarter scenario. The first line of each case starts with a positive integer N (1<=N<=1000), where N denotes the number of buildings in the head quarter. The next line contains a positive integer R, 1 ≤ R ≤ N*(N-1)/2, where R is the number of roads connecting two buildings. Each of the next R lines contains two distinct numbers, 0 ≤ u, v < N, this means there is a road connecting building u to building v. The buildings are numbered from 0 to N − 1. The last line of each case contains two integers 0 ≤ s, d < N. Where s denotes the building from where the mission starts and d denotes the building where they must meet.
You may assume that two buildings will be directly connected by at most one road. The input will be such that, it will be possible to go from any building to another by using one or more roads.
Output
For each case of input, there will be one line of output. It will contain the case number followed by the minimum time required to complete the mission. Look at the sample output for exact formatting.