| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1564 | Not That Kind of Graph [01] |
|
| 1568 | Critical Links [01] |
|
| 1572 | Play on Words [01] |
|
| 1576 | Domino Effect [01] |
|
Description
(Simulation)
Your task is to graph the price of a stock over time. In one unit of time, the stock can either Rise, Fall or stay Constant. The stock's price will be given to you as a string of R's, F's and C's. You need to graph it using the characters '/' (slash), '' (backslash) and '_' (underscore).
Input
The first line of input gives the number of cases, N (N ≦ 30). N test cases follow. Each one contains a string of at least 1 and at most 50 upper case characters (R, F or C).
Output
For each test case, output the line "Case #x:", where x is the number of the test case. Then print the graph, as shown in the sample output, including the x- and y-axes. The x-axis should be one character longer than the graph, and there should be one space between the y-axis and the start of the graph. There should be no trailing spaces on any line. Do not print unnecessary lines. The x-axis should always appear directly below the graph. Finally, print an empty line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
(Graphs and DFS)
In a computer network a link L, which interconnects two servers, is considered critical if there are at least two servers A and B such that all network interconnection paths between A and B pass through L. Removing a critical link generates two disjoint sub-networks such that any two servers of a sub-network are interconnected. For example, the network shown in figure 1 has three critical links that are marked bold: 0 - 1, 3 - 4 and 6 - 7.
Figure 1: Critical links
It is known that:
- the connection links are bi-directional;
- a server is not directly connected to itself;
- two servers are interconnected if they are directly connected or if they are interconnected with the same server;
- the network can have stand-alone sub-networks.
Write a program that finds all critical links of a given computer network.
Input
The program reads sets of data from a text file. Each data set specifies the structure of a network and has the format:
no_of_servers
server0 (no_of_direct_connections) connected_server ... connected_server
...
serverno_of_serveres - 1 (no_of_direct_connections) connected_server ... connected_server
The first line contains a positive integer no_of_servers (possibly 0) which is the number of network servers. The next no_of_servers lines, one for each server in the network, are randomly ordered and show the way servers are connected. The line corresponding to serverk, 0 ≦ k ≦ no_of_servers – 1, specifies the number of direct connections of serverk and the servers which are directly connected to serverk. Servers are represented by integers from 0 to no_of_servers – 1. Input data are correct. The first data set from sample input below corresponds to the network in figure 1, while the second data set specifies an empty network.
Input Specifications
- The number of test cases: T (T ≦ 20)
- The number of servers in the network: N (N ≦ 100)
- There is at most one link between any two servers.
Output
The result of the program is on standard output. For each data set the program prints the number of critical links and the critical links, one link per line, starting from the beginning of the line, as shown in the sample output below. The links are listed in ascending order according to their first element, break tie by the second element. The output for the data set is followed by an empty line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
(Eulerian circuit)
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open those doors. Because there is no other way to open the doors, the puzzle is very important for us.
There are 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 test cases. The number of them (T ≦ 20) 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 ≦ 100000). Then exactly N lines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that 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
Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase ``domino effect'' comes from).
While this is somewhat pointless with only a few dominoes, some people went to the opposite extreme in the early Eighties. Using millions of dominoes of different colors and materials to fill whole halls with elaborate patterns of falling dominoes, they created (short-lived) pieces of art. In these constructions, usually not only one but several rows of dominoes were falling at the same time. As you can imagine, timing is an essential factor here.
It is now your task to write a program that, given such a system of rows formed by dominoes, computes when and where the last domino falls. The system consists of several ``key dominoes'' connected by rows of simple dominoes. When a key domino falls, all rows connected to the domino will also start falling (except for the ones that have already fallen). When the falling rows reach other key dominoes that have not fallen yet, these other key dominoes will fall as well and set off the rows connected to them. Domino rows may start collapsing at either end. It is even possible that a row is collapsing on both ends, in which case the last domino falling in that row is somewhere between its key dominoes. You can assume that rows fall at a uniform rate.
Input
The input file contains descriptions of T domino systems (T ≤ 30). The first line of each description contains two integers: the number n of key dominoes (1 ≦ n < 500) and the number m of rows between them. The key dominoes are numbered from 1 to n. There is at most one row between any pair of key dominoes and the domino graph is connected, i.e. there is at least one way to get from a domino to any other domino by following a series of domino rows.
The following m lines each contain three integers a, b, and l, stating that there is a row between key dominoes a and b that takes l seconds to fall down from end to end.
Each system is started by tipping over key domino number 1.
The file ends with an empty system (with n = m = 0), which should not be processed.
Output
For each case output a line stating the number of the case (`System #1', `System #2', etc.). Then output a line containing the time when the last domino falls, exact to one digit to the right of the decimal point, and the location of the last domino falling, which is either at a key domino or between two key dominoes. If the last domino is between key domino A and key domino B, you should output the smaller one first and then the larger one. For example, if A = 5, B = 3, and the falling time of last domino is 3.0, you should output "The last domino falls after 3.0 seconds, between key dominoes 3 and 5.". Adhere to the format shown in the output sample. It is guaranteed that only one such output exists. Output a blank line after each system.