#P10124. [USACO18OPEN] Family Tree B
[USACO18OPEN] Family Tree B
题目描述
Farmer John 拥有一个传承数代的家族经营的农场,其中的奶牛的根源同样也可以在这个农场中追溯数代。通过检索古老的记录,Farmer John 好奇于现在的这群奶牛互相之间是什么关系。请帮帮他!
输入格式
输入的第一行包含 (),之后是两头奶牛的名字。每头奶牛的名字都是由至多 个大写字母(A-Z
)组成的字符串。Farmer John 好奇于这行输入中这两头奶牛之间的关系。
接下来的 行,每行包含两头奶牛的名字 和 ,表示 是 的母亲。
输出格式
输出包含一行,表示输入第一行指定的两头奶牛之间的关系(简单起见,在下面的例子中,将这两头奶牛称为 BESSIE 和 ELSIE)。下面是可能出现的不同种类的关系:
- 如果BESSIE和ELSIE的母亲是同一头奶牛,输出
SIBLINGS
。 - BESSIE 可能是 ELSIE 的直系后代,也就是说 ELSIE 是BESSIE 的母亲(
mother
),外祖母(grand-mother
),外曾外祖母(great-grand-mother
),外曾外曾外祖母(great-great-grand-mother
),等等。如果是这种情况,输出ELSIE is the (relation) of BESSIE
,其中(relation)
是适当的关系,比如great-great-grand-mother
。 - 如果 ELSIE 不是 BESSIE 的某个祖先或姐妹,但是是 BESSIE 的某个祖先的孩子,那么 ELSIE 就是 BESSIE 的姨母(
aunt
)。(译者注:英语原题在这里表述有误,供题人已作出声明。)如果 ELSIE 是 BESSIE 的外祖母的孩子,输出ELSIE is the aunt of BESSIE
;如果 ELSIE 是 BESSIE 的外曾外祖母的孩子,输出ELSIE is the great-aunt of BESSIE
;如果 ELSIE 是 BESSIE 的外曾外曾外祖母的孩子,输出ELSIE is the great-great-aunt of BESSIE
;以此类推。 - 如果 BESSIE 和 ELSIE 有任何其他的亲戚关系(也就是说,她们有共同的祖先),她们就是表姐妹,输出
COUSINS
。 - 如果 BESSIE 和 ELSIE 既没有共同的祖先,其中任何一头也不是另一头的直系后代,输出
NOT RELATED
。
下图描述了上述关系,你只需考虑这些关系。观察到有一些像是“甥女(niece
)”(姊妹的女儿)的关系是不必要的,这是由于如果 BESSIE 是 ELSIE 的甥女,那么 ELSIE 就是 BESSIE 的姨母。
7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER
BB is the great-aunt of AA