Output file:

Time limit:

Memory limit:

Physics teachers in high school often think that problems given as text are more demanding than pure
computations. After all, the pupils have to read and understand the problem first!

So they don't state a problem like "U=10V, I=5A, P=?" but rather like "You have an electrical circuit
that contains a battery with a voltage of U=10V and a light-bulb. There's an electrical current
of I=5A through the bulb. Which power is generated in the bulb?".

However, half of the pupils just don't pay attention to the text anyway. They just extract from the text
what is given: U=10V, I=5A. Then they think: "Which formulae do I know? Ah yes, P=U*I.
Therefore P=10V*5A=500W. Finished."

OK, this doesn't always work, so these pupils are usually not the top scorers in physics tests.
But at least this simple algorithm is usually good enough to pass the class. (Sad but true.)

Today we will check if a computer can pass a high school physics test. We will concentrate on the
P-U-I type problems first. That means, problems in which two of power, voltage and current are given and the third is wanted.

Your job is to write a program that reads such a text problem and solves it according to the simple algorithm given above.

Each test case will consist of one line containing exactly two data fields and some additional arbitrary words. A data field will be of the form I=

DataField ::= Concept '=' RealNumber [Prefix] Unit Concept ::= 'P' | 'U' | 'I' Prefix ::= 'm' | 'k' | 'M' Unit ::= 'W' | 'V' | 'A'Additional assertions:

- The equal sign ('=') will never occur in an other context than within a data field.
- There is no whitespace (tabs,blanks) inside a data field.
- Either P and U, P and I, or U and I will be given.

- a line saying "Problem #
*k*" where*k*is the number of the test case - a line giving the solution (voltage, power or current, dependent on what was given), written without a prefix and with two decimal places as shown in the sample output
- a blank line

3 If the voltage is U=200V and the current is I=4.5A, which power is generated? A light-bulb yields P=100W and the voltage is U=220V. Compute the current, please. bla bla bla lightning strike I=2A bla bla bla P=2.5MW bla bla voltage?

Problem #1 P=900.00W Problem #2 I=0.45A Problem #3 U=1250000.00V

Output file:

Time limit:

Memory limit:

Within *Settlers of Catan*, the 1995 German game of the year,
players attempt to dominate an island by building roads, settlements
and cities across its uncharted wilderness.

You are employed by a software company that just has decided to develop
a computer version of this game, and you are chosen to implement one
of the game's special rules:

When the game ends, the player who built the longest road gains two extra victory points.The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).

Compared to the original game, we will solve a simplified problem here:
You are given a set of nodes (cities) and a set of edges (road segments)
of length 1 connecting the nodes.

The longest road is defined as the longest path within the network that
doesn't use an edge twice. Nodes may be visited more than once, though.

Example: The following network contains a road of length 12.

o o--o o \ / \ / o--o o--o / \ / \ o o--o o--o \ / o--o

The first line of each test case contains two integers: the number of nodes

Input will be terminated by two values of 0 for

3 2 0 1 1 2 15 16 0 2 1 2 2 3 3 4 3 5 4 6 5 7 6 8 7 8 7 9 8 10 9 11 10 12 11 12 10 13 12 14 0 0

2 12

Output file:

Time limit:

Memory limit:

*Queues* and *Priority Queues* are data structures which are
known to most computer scientists. The *Team Queue*, however, is not
so well known, though it occurs often in everyday life.
At lunch time the queue in front of the Mensa is a team queue, for example.

In a team queue each element belongs to a team. If an element enters the
queue, it first searches the queue from head to tail to check if some of its
*teammates* (elements of the same team) are already in the queue.
If yes, it enters the queue right behind them.
If not, it enters the queue at the tail and becomes the new last element (bad luck).
Dequeuing is done like in normal queues: elements are processed from head
to tail in the order they appear in the team queue.

Your task is to write a program that simulates such a team queue.

Finally, a list of commands follows. There are three different kinds of commands:

- ENQUEUE x - enter element x into the team queue
- DEQUEUE - process the first element and remove it from the queue
- STOP - end of test case

**Warning:**
A test case may contain up to 200000 (two hundred thousand) commands, so the implementation
of the team queue should be efficient: both enqueing and dequeuing of an element should only
take constant time.

2 3 101 102 103 3 201 202 203 ENQUEUE 101 ENQUEUE 201 ENQUEUE 102 ENQUEUE 202 ENQUEUE 103 ENQUEUE 203 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 2 5 259001 259002 259003 259004 259005 6 260001 260002 260003 260004 260005 260006 ENQUEUE 259001 ENQUEUE 260001 ENQUEUE 259002 ENQUEUE 259003 ENQUEUE 259004 ENQUEUE 259005 DEQUEUE DEQUEUE ENQUEUE 260002 ENQUEUE 260003 DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 0

Scenario #1 101 102 103 201 202 203 Scenario #2 259001 259002 259003 259004 259005 260001

Output file:

Time limit:

Memory limit:

A boolean matrix has the *parity property* when each row
and each column has an even sum, i.e. contains an even number of bits
which are set. Here's a 4 x 4 matrix which has the parity property:

1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1The sums of the rows are 2, 0, 4 and 2. The sums of the columns are 2, 2, 2 and 2.

Your job is to write a program that reads in a matrix and checks if
it has the parity property. If not, your program should check if the
parity property can be established by changing only one bit. If this
is not possible either, the matrix should be classified as *corrupt*.

4 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 4 1 0 1 0 0 0 1 0 1 1 1 1 0 1 0 1 4 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0

OK Change bit (2,3) Corrupt

Output file:

Time limit:

Memory limit:

In 1742, Christian Goldbach, a German amateur mathematician, sent a
letter to Leonhard Euler in which he made the following conjecture:

Every even number greater than 4 can beFor example:

written as the sum of two odd prime numbers.

- 8 = 3 + 5. Both 3 and 5 are odd prime numbers.
- 20 = 3 + 17 = 7 + 13.
- 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.

Each test case consists of one even integer

Input will be terminated by a value of 0 for

8 20 42 0

8 = 3 + 5 20 = 3 + 17 42 = 5 + 37

Output file:

Time limit:

Memory limit:

The first round of the Soccer World Championship in Germany is coming to an end.
16 countries are remaining now, among which the winner is determined by the following tournament:

1 Germany ----+ +-- ? --+ 2 Sweden -----+ | +-- ? --+ 3 Mexico -----+ | | +-- ? --+ | 4 Argentina --+ | +-- ? --+ 5 Ukraine ----+ | | +-- ? --+ | | 6 Switzerland + | | | +-- ? --+ | 7 Italy ------+ | | +-- ? --+ | 8 Austraila --+ | +-- World Champion 9 Brazil -----+ | +-- ? --+ | 10 Ghana ------+ | | +-- ? --+ | 11 France -----+ | | | +-- ? --+ | | 12 Spain ------+ | | +-- ? --+ 13 Portugal ---+ | +-- ? --+ | 14 Holland ----+ | | +-- ? --+ 15 England ----+ | +-- ? --+ 16 Ecuador ----+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 Italy wins against Australia with 80%, Ukraine against Switzerland with 60%, Italy against Ukraine with 70% and Italy against Switzerland with 90%, then the probability that Italy 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 '06.

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 p

Note that matches may not end with a draw, i.e. p

Brazil Chile Nigeria Denmark Holland Yugoslavia Argentina England Italy Norway France Paraguay Germany Mexico Romania Croatia 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 40 55 40 50 45 40 40 55 35 45 30 45 30 45 40 40 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 35 50 35 45 40 35 35 50 30 40 25 40 25 40 35 35 55 70 55 65 60 55 55 70 50 60 45 60 45 60 55 55 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 60 75 60 70 65 60 60 75 55 65 50 65 50 65 60 60 45 60 45 55 50 45 45 60 40 50 35 50 35 50 45 45 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50 50 65 50 60 55 50 50 65 45 55 40 55 40 55 50 50

Brazil p=8.54% Chile p=1.60% Nigeria p=8.06% Denmark p=2.79% Holland p=4.51% Yugoslavia p=7.50% Argentina p=8.38% England p=1.56% Italy p=9.05% Norway p=3.23% France p=13.72% Paraguay p=3.09% Germany p=13.79% Mexico p=3.11% Romania p=5.53% Croatia p=5.53%