Connection Status:
Competition Arena > NextRuler

NextRuler

SRM 125 · 2002-12-16 · by Yarin

SRM 125 · 2002-12-16 · by Yarin
Class Name: NextRuler
Return Type: String
Method Name: bestClaim
Arg Types: (vector<string>, string, vector<string>)
Problem Statement

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).

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 " " 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 (ASCII 32).
Examples
0)
{"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.

1)
{"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.

2)
{"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.

3)
{"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.

4)
{"B A xx","C B xx","D C xx","E D xx","F E xx","G F xx","H G xx","I H xx","J I xx","K J xx","L K xx","M L xx","N M xx","O N xx","P O xx","Q P xx","R Q xx","S R xx","T S xx","U T xx","V U xx","W V xx","X W xx","Y X xx","Z Y xx","a Z xx","b a xx","c b xx","d c xx","e d xx","f e xx","g f xx","h g xx","i h xx","j i xx","k j xx","l k xx","m l xx","n m xx","o n xx","p o xx","q p xx","r q xx","s r xx","t s xx","u t xx","v u xx","w v xx","x w xx","y x A"}
"A"
{"B","y"}
Returns: "y"

Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NextRuler with a public method string bestClaim(vector<string> relation, string originalruler, vector<string> claimants) · 95 test cases · 2 s / 256 MB per case

Submitting as anonymous