Paul the Chef loves recursive salads. For example, his favorite salad,
“razduv” (blow up) consists of 30% cucumbers, 20% tomatoes and
50% salad “razgon” (drive on). The “razgon” salad consists
of 40% bread, 20% cucumbers and 40% “razduv” salad.
For each of Paul’s favorite salads, we know its formula as a percentage
of all its components. A component of a salad could be a basic ingredient or
another salad. Your task is to find the formulas of Paul’s salads where
all components are basic ingredients.
Input
Input data contains formulas of Paul’s salads.
The names of the salads and basic ingredients consist of at most 10
small English letters. If some component has a formula, then it is a
salad, in the other case it is a basic ingredient. All formulas are listed
in the lexicographical order of salad’s names. The components in each
formula are also listed in the lexicographical order. All the percentages
are integers from 1 to 100, the sum of percentages in one formula is equal
to 100. Overall, there are at most 10 distinct salads and at most 10
distinct basic ingredients. Follow the input data format from the sample tests.
Output
Output formulas of Paul’s salads depending only on the basic ingredients,
not on the other salads. Formulas and the components in each formula
should be listed in the lexicographical order. Percentages should be
output with an absolute or relative error no more than 10−3.
The sum of percentages in each formula should be equal to 100.
If a salad does not contain some basic ingredient, the name of this
ingredient should be output with a percentage 0. We guarantee that there
exists exactly one solution for our input data.
Samples
input | output |
---|
razduv : cucumber 30 razgon 50 tomato 20
razgon : bread 40 cucumber 20 razduv 40
| razduv : bread 25.0 cucumber 50.0 tomato 25.0
razgon : bread 50.0 cucumber 40.0 tomato 10.0
|
razduv : cucumber 100
razgon : tomato 100
| razduv : cucumber 100.0 tomato 0
razgon : cucumber 0 tomato 100.0
|
Problem Author: Pavel Klimov
Problem Source: Open Ural FU Championship 2013