NextRuler | Topcoder Archive

Problem Statement

When a ruler in a country dies, there are several ways of selecting a new ruler. In this problem, we will consider the following method: for every person claiming the throne, you measure the amount of blood in his veins that comes from the original ruler (the amount of royal blood). A person gets half the blood from the father, the other half from the mother. So, a child to the original ruler would have 1/2 royal blood, that child's child with another parent who is not of royal lineage would have 1/4 royal blood etc.

Given a list of child-parent-parent relations, you should determine which claimant has the best claim to the throne. That is, the claimant with most royal blood. Each relation will be described as a string in the following format: (quotes are for clarity only)


"<child> <parent> <parent>"

There will be exactly one space between each term, and no leading or trailing spaces.

Create a class NextRuler containing the method bestClaim which takes a String[] relations, a String originalruler and a String[] claimants and returns a String containing the claimant that has the most royal blood. If there are several claimants with the same amount of royal blood, return the first one (in claimants).

Definition

Class:: NextRuler
Method:: bestClaim
Parameters:: String[], String, String[]
Returns:: String
Method signature:: String bestClaim(String[] relation, String originalruler, String[] claimants)
(be sure your method is public)

Notes

Two persons with the same name are, in fact, the same person.
It's possible for people who are closely related to have a child together (after all, royal families are known for intermarriage).
It's possible for someone to have children with several different partners.
Since the actual sex of a person isn't considered, relations like that in example 1 are possible in this problem.
If a parent is not listed as a child, then the parent has no royal blood (except, of course, for the original ruler).
All names are case sensitive.

Constraints

relations contains between 1 and 50 elements, inclusive.
claimants contains between 1 and 50 elements, inclusive.
Each element in relations will be in the format "<child> <parent> <parent>" without leading or trailing spaces.
Each child will have two unique parents, and nobody will be mentioned as a child more than once.
No one will be a descendent from himself.
The original ruler will not appear as the child in relations.
The original ruler will not appear in claimants.
No one will appear more than once in the claimants.
At least one claimant will be a descendent from the original ruler.
The original ruler as well as all claimants will appear in at least one of the relations (as either child or parent).
Names of people will be between 1 and 10 characters long (inclusive) and only contain upper and lower case letters ('A'-'Z', 'a'-'z').
All characters in the input parameters will only contain the ASCII characters 'A'-'Z', 'a'-'z' and <space> (ASCII 32).

Examples

```
{"CharlesI EdwardI Diana",
 "Philip CharlesI Mistress",
 "Wilhelm Mary Philip",
 "Matthew Wilhelm Helen",
 "EdwardII CharlesI Laura",
 "Alice Laura CharlesI",
 "Helen Alice Bernard",
 "HenriI EdwardII Roxane",
 "CharlesII Elizabeth HenriI"}
```
```
"EdwardI"
```
```
{"CharlesII","Matthew"}
```
```
Returns: "Matthew"
```
The relations can be pictured like this: EdwardI-----Diana | Laura-------CharlesI-----------------Mistress /\ | Roxane--------EdwardII Alice-------Bernard Philip-------Mary | | | Elizabeth-----HenriI Helen----------------Wilhelm | | CharlesII Matthew The royal blood for each of the persons above is: CharlesI 1/2 EdwardII 1/4 Alice 1/4 Philip 1/4 HenriI 1/8 Helen 1/8 Wilhelm 1/8 Matthew 1/8 CharlesII 1/16 Matthew has more royal blood than CharlesII, so the method should return Matthew.
```
{"A P Q","B Q R","C R P"}
```
```
"Q"
```
```
{"A","B","C"}
```
```
Returns: "A"
```
P, Q and R all have a child with each other, not something that would be possible for human beings, but in this problem it's possible. Child A and B have 1/2 royal blood, and since A comes first in the claimant list, the method should return A.

{"B A x","C A x","D B y","E B y","F C z","G C z","H E F"}

"A"

{"G","H","D"}

Returns: "G"

The royal blood for all three claimants are 1/4, so the method should return G.

```
{"B A x","C B x","D C x","E D x","F E A"}
```
```
"A"
```
```
{"B","F"}
```
```
Returns: "F"
```
The royal blood in B is 1/2, while in F it's 17/32, so the method should return F.

{"b c d",
 "C D E",
 "Z a b",
 "B C D",
 "G H I",
 "S T U",
 "Y Z a",
 "M N O",
 "I J K",
 "d e f",
 "K L M",
 "V W X",
 "N O P",
 "O P Q",
 "P Q R",
 "R S T",
 "a b c",
 "U V W",
 "D E F",
 "Q R S",
 "J K L",
 "W X Y",
 "A B C",
 "L M N",
 "E F G",
 "H I J",
 "X Y Z",
 "T U V",
 "F G H",
 "c d e"}

"f"

{"V","D","B","c","K"}

Returns: "V"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.