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

Ural Regional School Programming Contest 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. ManBearPig

Time limit: 0.5 second
Memory limit: 64 MB
It was an early winter morning at South Park. As usual, adults were hurrying to work and children were hurrying to school. Stan, Kyle, Kenny, and Eric stood at a bus stop waiting for the school bus. The day promised to be dull and boring.
The boys didn't know that they would meet an interesting person that day. It all started when the school counselor gathered the children in the gymnasium and announced: “Attention, students, we have a very special guest speaker today. Who can tell me the name of our country's last vice-president?”
Of course, none of the children knew that his name was Al Gore. It turned out a bit later that, possibly, it was for the better.
The man mounted the platform and said: “Thanks, Mr. Mackey, and good morning to South Park Elementary! I am here to tell you about the single biggest threat to our planet. You see, there is something out there which threatens our very existence and may be the end to the human race as we know it. I'm talking, of course, about ‘ManBearPig.’ It is a creature which roams the Earth alone. It is half man, half bear, and half pig. Some people say that ManBearPig isn't real. Well, I'm here to tell you now, ManBearPig is very real. ManBearPig doesn't care who you are and what you've done. ManBearPig just wants to get you. But have no fear, because I am here to save you. And someday, when the world is rid of ManBearPig, everyone will say, ‘Thank you, Al Gore!’”
Of course, nobody paid attention to Gore's words. Everybody just shrugged their shoulders and went to their classes. But in the evening Eric Cartman suddenly understood that Al Gore had said complete nonsense.
Judge for yourself, how could one creature consist of three halves of other creatures? Eric told that to Kenny, but Kenny dismissed it by saying that Gore, evidently, had meant one third of each creature. However, Eric was right. Indeed, there is no lineage that could lead to ManBearPig containing equal parts of pig, bear, and man.
A lineage of a creature is a sequence of interbreedings of creatures that leads to the birth of this creature. When creature A is interbreeded with creature B, a new creature is born, which consists of A and B. If creature A contained a percent of some animal and creature B contained b percent of the same animal, then the new creature contains (a + b) / 2 percent of that animal.
Now Eric wants to construct a possible lineage of a creature by the information on which animals and in which proportions are contained in this creature.


The first line contains the name of a creature. It consists of lowercase English letters and hyphens and has length in the range from 1 to 200. The hyphens in this name separate the names of animals. Each animal has a nonempty name and appears in the name of the creature at most once. The creature consists of at least one and at most ten different animals. The second line contains a space-separated list of fractions of the form a/b (1 ≤ ab ≤ 1500). The i-th fraction in this list is the part of the creature that the i-th animal makes up. The sum of the fractions is equal to one.


Output a lineage of the creature in the form of a consecutive description of how its ancestors and the creature itself were born. In the first line output the number n of lines in the lineage (1 ≤ n ≤ 10000). After that output n − 1 lines. The k-th of these lines must describe the k-th ancestor of the creature. If the k-th ancestor is an animal, then the line must contain its name only. If this ancestor was born as a result of interbreeding of two of the earlier-described ancestors, then the line must contain a pair of integers in the range from 1 to k − 1. The integers are the numbers of lines in the lineage where these ancestors are described. In the last line output, in the same format, how the creature given in the input was born. All the described ancestors of the creature must appear in at least one interbreeding. If there are several possible lineages, output any of them. If it is impossible to construct the required lineage, output the line “No solution”.


1/2 1/4 1/4
1 2
4 5
3 6
1/3 1/3 1/3
No solution
Problem Author: Fedor Fominykh (prepared by Ivan Burmistrov)
Problem Source: Ural Regional School Programming Contest 2009
To submit the solution for this problem go to the Problem set: 1730. ManBearPig