ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Paul’s Salads

Time limit: 0.5 second
Memory limit: 64 MB
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1986. Paul’s Salads