| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1576 | Domino Effect [01] |
|
| 7345 | PD - Delivery Debacle |
|
| 7420 | Matrix Chain Multiplication |
|
| 7433 | France '98 |
|
| 7443 | HTML |
|
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.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Wolfgang Puck has two very peculiar habits:
I. He only makes two shapes of cakes. One is square and has an area of one unit. The other is L-shaped and has an area of three units.
II. He will only deliver cakes packed in very specific box sizes. The boxes are always 2 units wide and are of varying length.
One day Wolfgang wondered in how many different ways he can pack his cakes into certain sized boxes. Can you help him?
.png)
The precise sizes of the cakes Wolfgang makes and one way to pack them in a box of length 6.
The five ways to pack a box of length 2.
Input
The input begins with t, the number of different box lengths. The following t lines contain an integer n (1 <= n <= 40).
Output
For each n output on a separate line the number of different ways to pack a 2-by-n box with cakes described above. Output is guaranteed to be less than 1018.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Suppose you have to evaluate an expression like A × B × C × D × E where A, B, C, D and E are matrices.
Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose. For example, let A be a 50 × 10 matrix, B a 10 × 20 matrix and C a 20 × 5 matrix. There are two different strategies to compute A × B × C, namely (A × B) × C and A × (B × C). The first one takes 15000 elementary multiplications, but the second one only 3500.
Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.
Input
Input consists of two parts: a list of matrices and a list of expressions. The first line of the input file contains one integer n (1 ≤ n ≤ 26), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix. The second part of the input file strictly adheres to the following syntax (given in EBNF):
SecondPart = Line { Line }
Line = Expression
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
Output
For each expression found in the second part of the input file, print one line containing the word "error" if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Today the first round of the Soccer World Championship in France is coming to an end. 16 countries are remaining now, among which the winner is determined by the following tournament:
1 Brazil -----+
+-- ? --+
2 Chile ------+ |
+-- ? --+
3 Nigeria ----+ | |
+-- ? --+ |
4 Denmark ----+ |
+-- ? --+
5 Holland ----+ | |
+-- ? --+ | |
6 Yugoslavia -+ | | |
+-- ? --+ |
7 Argentina --+ | |
+-- ? --+ |
8 England ----+ |
+-- World Champion
9 Italy ------+ |
+-- ? --+ |
10 Norway -----+ | |
+-- ? --+ |
11 France -----+ | | |
+-- ? --+ | |
12 Paraguay ---+ | |
+-- ? --+
13 Germany ----+ |
+-- ? --+ |
14 Mexico -----+ | |
+-- ? --+
15 Romania ----+ |
+-- ? --+
16 Croatia ----+
For each possible match A vs. B between these 16 nations, you are given the probability that team A wins against B. This (together with the tournament mode displayed above) is sufficient to compute the probability that a given nation wins the World Cup. For example, if Germany wins against Mexico with 80%, Romania against Croatia with 60%, Germany against Romania with 70% and Germany against Croatia with 90%, then the probability that Germany reaches the semi-finals is 80% * (70% * 60% + 90% * 40%) = 62.4%.
Your task is to write a program that computes the chances of the 16 nations to become the World Champion '98.
Input
The input file will contain just one test case.
The first 16 lines of the input file give the names of the 16 countries, from top to bottom according to the picture given above.
Next, there will follow a 16 x 16 integer matrix P where element pijgives the probability in percent that country #i defeats country #j in a direct match. Country #i means the i-th country from top to bottom given in the list of countries. In the picture above Brazil is #1 and Germany is #13, so p1,13=55 would mean that in a match between Brazil and Germany, Brazil wins with a probability of 55%.
Note that matches may not end with a draw, i.e. pij + pji = 100 for all i,j.
Output
Output 16 lines of the form "XXXXXXXXXX p=Y.YY%", where XXXXXXXXXX is the country's name, left-justified in a field of 10 characters, and Y.YY is their chance in percent to win the cup, written to two decimal places. Use the same order of countries like in the input file.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
If you ever tried to read a html document on a Macintosh, you know how hard it is if no Netscape is installed.
Now, who can forget to install a HTML browser? This is very easy because most of the times you don't need one on a MAC because there is a Acrobate Reader which is native to MAC. But if you ever need one, what do you do?
Your task is to write a small html-browser. It should only display the content of the input-file and knows only the html commands (tags)
Input
The input consists of a text you should display. This text consists of words and HTML tags separated by one or more spaces, tabulators or newlines.
A word is a sequence of letters, numbers and punctuation. For example, "abc,123" is one word, but "abc, 123" are two words, namely "abc," and "123". A word is always shorter than 81 characters and does not contain any '<' or '>'. All HTML tags are either
Output
You should display the the resulting text using this rules:
- If you read a word in the input and the resulting line does not get longer than 80 chars, print it, else print it on a new line.
- If you read a
- If you read a
The last line is ended by a newline character.