| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11015 | Mutant Flatworld Explorers |
|
| 11017 | Friends |
|
| 11018 | Play on Words |
|
| 11019 | The Gossipy Gossipers Gossip Gossips |
|
Description
Given the dimensions of a rectangular grid and a sequence of robot positions and instructions, you are to write a program that determines for each sequence of robot positions and instructions the final positions of the robot.
A robot position consists of a grid coordinate (a pair of integers: x-coordinate followed by y-coordinate) and an orientation (N, S, E, W for north, south, east, and west). A robot instruction is a string of the letters 'L', 'R', and 'F' which represent, respectively, the instructions:
- Left: the robot turns left 90 degrees and remains on the current grid point.
- Right: the robot turns right 90 degrees and remains on the current grid point.
- Forward: the robot moves forward one grid point in the direction of the current orientation and maintains the same orientation.
The direction North corresponds to the direction from grid point (x, y) to grid point (x, y + 1).
Since the grid is rectangular and bounded, a robot that moves "off" an edge of the grid is lost forever. However, lost robots leave a robot "scent" that prohibits future robots from dropping off the world at the same grid point. The scent is left at the last grid position the robot occupied before disappearing over the edge. An instruction to move "off" the world from a grid point from which a robot has been previously lost is simply ignored by the current robot.
Input
The first line of input is the upper-right coordinates of the rectangular world, the lower-left coordinates are assumed to be (0, 0).
The remaining input consists of a sequence of robot positions and instructions (two lines per robot). A position consists of two integers specifying the initial coordinates of the robot and an orientation (N, S, E, W), all separated by white space on one line. A robot instruction is a string of the letters 'L', 'R', and 'F' on one line. The length of instructions for each robot is at least 1.
Each robot is processed sequentially, i.e., finishes executing the robot instructions before the next robot begins execution.
Input is terminated by end-of-file.
You may assume that all initial robot positions are within the bounds of the specified grid. The maximum value for any coordinate is 50. All instruction strings will be less than 101 characters in length.
Output
For each robot position/instruction in the input, the output should indicate the final grid position and orientation of the robot. If a robot falls off the edge of the grid the word ''LOST'' should be printed after the position and orientation.
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
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word 'acm' can be followed by the word 'motorola'. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T (≤ 20) test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number N that indicates the number of plates (1 ≤ N ≤ 30,000). Then exactly N lines follow, each containing a single word. Each word contains at least two and at most 1,000 lowercase characters, which means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence 'Ordering is possible.'. Otherwise, output the sentence 'The door cannot be opened.'
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’.