Figure 1: Example family tree.
Figure 1: Example family tree.
Distribute an inheritance among the heirs.
A rich person buries a treasure chest in their back yard and dies. Years (perhaps generations) later, the chest is unearthed, its contents are sold, and the proceeds are distributed among the living descendants. To this end, a family tree is drawn. The family tree starts with the originator (who buried the treasure) and traces the genealogy down to the currently living descendents.
Any person X who appears in the family tree along with one or more descendants, is deceased. The share of the inheritance of any such person X is divided equally among those children of X who are either currently living or produced (directly or indirectly) currently living descendants. (Any deceased descendants of the originator who did not produce further descendants are omitted from the family tree.)
Any person Y who is shown in the family tree without descendants, is a currently living descendant. Your goal is to determine the fractional share of the inheritance for each such person Y. The sum of the shares must of course equal 1. (Such a person Y may in reality have some living descendants, but they will not be shown in the family tree.)
Consider, for example, the family tree of figure 1. The originator is Judith. The currently living descendants (shown without children in the family tree) are Dick, Cathy, Maggie, Carl, and Bob. Their respective shares of the inheritance are: 1/3, 1/6, 1/12, 1/12 and 1/3.
The input will contain data for a number of problem instances. For each problem instance, the input will represent a family tree on one or more lines. The first problem instance in the sample input (below) corresponds to the family tree of Figure 1.
The first line will begin with the name of the originator, followed by a list of the originator’s children (there will be at least one).
There will be one additional line for each deceased descendant. Each of those lines will begin with the name of the deceased descendant, followed by the list of his or her children.
Each problem instance will be terminated with a line containing a single asterisk (*). The input will be terminated with a line containing two asterisks.
Notes:
For each problem instance, the output will consist of the list of living descendants from the family tree, one name per line. Each name will be followed by a colon, one blank space, and the corresponding fractional share of the inheritance, in the form 1/N.
You may assume the input will be such that this N will be within the bounds of 32-bit (signed) integer variables.
The names will be listed in the same order in which they appear in the input.
The output will not contain any blank spaces, except the one blank space following each colon.
Each problem instance will be followed by a line of 20 hyphens (-).
Judith Dick Ethel Linda Ethel Cathy Jack Jack Maggie Carl Linda Bob * Bill Jill * Jackie Rod Sarah Rod Albert Albert Carol Susie Max * **
Dick: 1/3 Cathy: 1/6 Maggie: 1/12 Carl: 1/12 Bob: 1/3 ------------------- Jill: 1/1 ------------------- Sarah: 1/2 Carol: 1/6 Susie: 1/6 Max: 1/6 -------------------