| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1544 | 23 Out of 5 [01] |
|
| 1580 | The Net [01] |
|
| 1584 | Page Hopping [01] |
|
| 1588 | Fans and Gems [01] |
|
Description
Your task is to write a program that can decide whether you can find an arithmetic expression consisting of five given numbers ai (1 ≤ i ≤ 5) that will yield the value 23.
For this problem we will only consider arithmetic expressions of the following from:
where 
:{1,2,3,4,5} -> {1,2,3,4,5} is a bijective function and 
{+,-,*} (1 ≤ i ≤ 4)
Input
The Input consists of 5-Tupels of positive Integers, each between 1 and 50.
Input is terminated by a line containing five zero's. This line should not be processed.
Output
For each 5-Tupel print "Possible" (without quotes) if their exists an arithmetic expression (as described above) that yields 23. Otherwise print "Impossible".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Taking into account the present interest in the Internet, a smart information routing becomes a must. This job is done by routers situated in the nodes of the network. Each router has its own list of routers which are visible for him (so called ``routing table"). It is obvious that the information should be directed in the way which minimizes number of routers it has to pass (so called ``hop count").
Your task is to find an optimal route (minimal hop count) for the given network form the source of the information to its destination.
Input
First line contains number of routers in the network (n). Next n lines contain description of the network. Each line contains router ID, followed by a hyphen and comma separated list of IDs of visible routers. The list is sorted in ascending order. Next line contains a number of routes (m) you should determine. The consecutive m lines contain starting and ending routers for the route separated by a single space.
Input data may contain descriptions of many networks.
Output
For each network you should output a line with 5 hyphens and then, for each route, a list of routers passed by information sent from starting to destination routers.
In case passing of information is impossible (no connection exists) you should output a string ``connection impossible". In case of multiple routes with the same `hop count' the one with lower IDs should be outputted (in case of route form router 1 to 2 as 1 3 2 and 1 4 2 the 1 3 2 should be outputted).
Assumptions: A number of routers is not greater than 300 and there are at least 2 routers in the network. Each routers ``sees" no more than 50 routers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It was recently reported that, on the average, only 19 clicks are necessary to move from any page on the World Wide Web to any other page. That is, if the pages on the web are viewed as nodes in a graph, then the average path length between arbitrary pairs of nodes in the graph is 19.
Given a graph in which all nodes can be reached from any starting point, your job is to find the average shortest path length between arbitrary pairs of nodes. For example, consider the following graph. Note that links are shown as directed edges, since a link from page a to page b does not imply a link from page b to page a.
The length of the shortest path from node 1 to nodes 2, 3, and 4 is 1,1, and 2 respectively. From node 2 to nodes 1, 3 and 4, the shortest paths have lengths of 3, 2, and 1. From node 3 to nodes 1, 2, and 4, the shortest paths have lengths of 1, 2, and 3. Finally, from node 4 to nodes 1, 2, and 3 the shortest paths have lengths of 2, 3, and 1. The sum of these path lengths is 1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22. Since there are 12 possible pairs of nodes to consider, we obtain an average path length of 22/12, or 1.833 (accurate to three fractional digits).
Input
The input data will contain multiple test cases. Each test case will consist of an arbitrary number of pairs of integers, a and b, each representing a link from a page numbered a to a page numbered b. Page numbers will always be in the range 1 to 100. The input for each test case will be terminated with a pair of zeroes, which are not to be treated as page numbers. An additional pair of zeroes will follow the last test case, effectively representing a test case with no links, which is not to be processed. The graph will not include self-referential links (that is, there will be no direct link from a node to itself), and at least one path will exist from each node in the graph to every other node in the graph.
Output
For each test case, determine the average shortest path length between every pair of nodes, accurate to three fractional digits. Display this length and the test case identifier (they're numbered sequentially starting with 1) in a form similar to that shown in the sample output below.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Tomy's fond of a game called 'Fans and Gems' (also known as Gravnic). In the game, he can use fans to collect gems, but he's satisfied with his play only if all the gems are collected with minimal number of steps. The game is played as following:
There are three kinds of gems, one colored red, one colored green and one colored blue. There are walls in the space, as you see. There are also virtual fans everywhere in the game, but you cannot see them. What you can do each time is to select a DIRECTION to which the fans should blow. There are only four directions possible: UP, DOWN, LEFT and RIGHT. Then, the fans will work, pushing all the gems to fly to the selected direction at the same speed, until they cannot move further(blocked by the wall, other gems or a flyer). Then, if there are some gems touching some same-colored gem(touching means adjacent in one of the four directions), they disappear simultaneously. Note that the fans are still working, so some gems may go on moving in that direction after some gems disappeared. The fans stop working when all the gems cannot move any more, and none of them should disappear. There may be some flyers that can be moved by the fans, but they can NEVER disappear.
You are to write a program that finds the minimal number of operations to make all the gems disappear.
Input
The input file begins with an integer T, indicating the number of test cases. (1 ≤ T ≤ 15) Each test case begins with two integers N, M, indicating the height and width of the map. (1 ≤ N ≤ 12, 1 ≤ M ≤ 20) In the following N lines, each line contains M characters describing the map. There is one line after each map, ignore them. Spaces denotes empty square, '#' denotes a wall, '1' denotes a red gem, '2' denotes a green gem, '3' denotes a blue gem, and '@' denotes a flyer. It's guaranteed that the four sides of the map are all walls. There is at least one gem in the map, and no two same-colored gems will touch each other at the beginning of the game.
Output
You should print a single line for each case. If there is a solution, write the shortest operation sequence in a string. The ith character must be from the set {'U','D','L','R'}, describing ith operation. The four characters represent UP, DOWM, LEFT, RIGHT respectively. If there are more than one solution, choose the lexicographical smallest one, if there are no solution, output -1 on the line. When a solution exists, you need only 18 or fewer steps to carry it out.