Woburn Challenge 2002

Problem 3: The Big Book of Recipes

So how is the monkeys' meeting going, you ask? Well, the Head-Monkey is quite big on food and whenever there's a meeting atop the Enchanted Tree, it is a necessity that dinner is served (pun intended). What the monkeys don't realize is that the Head-Monkey is not really a good cook. But then, how many army leaders are good cooks? The answer is, none. This time, the Head-Monkey has purchased a cookbook. The cookbook has a certain number of recipes, but any recipe may require an ingredient which must be prepared according to some other recipe! This is all quite confusing for the Head-Monkey. She wants you to tell her how much of each base ingredient she needs for her recipe.

Input

The first line of input contains a single integer, T (1 ≤ T ≤ 50), indicating the number of test cases.
The first line of each test case will contain N (1 ≤ N ≤ 20), the total number of ingredients to follow. For each ingredient, there follows a line with that ingredients name - if the ingredient is a basic ingredient it will be in lowercase letters, if there is a recipe in terms of other ingredients for it, its name will be in capital letters.
For each non-basic ingredient, a recipe for one serving of that ingredient will follow (format: an integer k, 1 ≤ k ≤ 20, indicating the number of ingredients in that recipe, then a series of lines of the form [number of servings of ingredient required, _space_, ingredient required]).
Finally, there will be an ingredient name - you are to determine the amount of each basic ingredient required to make one serving of that ingredient.

Output

A series of lines of the form [number of servings of ingredient required, _space_, ingredient required], containing only basic ingredients. Output them in the same order as they were listed in the input.
Leave a blank line between test cases.

Sample Input 1 10 CHEESE milk SAMMICH salt turkey ham egg vinegar MAYO bread 2 1.5 milk 0.25 salt 5 2.2 CHEESE 1 bread 1 turkey 1 ham 0.3 MAYO 3 0.2 egg 0.1 vinegar 0.1 salt SAMMICH

[recipe for CHEESE] [recipe for SAMMICH] [recipe for MAYO] [thing we want to make]

Sample Output 3.3 milk 0.58 salt 1 turkey 1 ham 0.06 egg 0.03 vinegar 1 bread

Note: The comments off to the side won't appear in the input file!

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)