f890: DD的族譜
Tags : DD 拓樸排序
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-24 13:46

Content

DD人物介紹 : https://zerojudge.tw/ShowProblem?problemid=f754 

DD在這疫情嚴峻的時間裡,因為沒朋友想和他視訊聊天,於是他無聊時便在家裡亂翻家裡的東西,他無意間翻到家裡的一卷族譜,但他看不太懂字,於是便問他爸這是什麼,爸爸便跟他解釋什麼是族譜,並將每一條血緣或姻親關係告訴他,DD藉由一條條的關係也自己畫出了一個族譜,爸爸看DD很閒,便給他一項任務,告訴他家裡每個人的關係,希望DD能將每個人的年紀大小排出順序。

  以下是一些簡單的規則:

1.長輩一定比晚輩大(不用考慮因太晚生或太早生造成晚輩年紀比長輩大)

2.哥哥姊姊比弟弟妹妹大

3.若同輩間分不出來誰大誰小,年齡由D最大,接著年齡由大而小依序為:A、B、C、E、F……W、X、Y、Z

4.一個人不會跨輩分

  不過,爸爸油時也會拿錯誤的族譜考DD,請DD分辨出來,以下是幾種錯誤狀況:

1.輩分混亂(e.g.A是B的爸爸,B是C的爸爸,C是A的女兒)

2.年齡混亂(e.g.A是B的哥哥,C是B的妹妹,C是A的姐姐)

3.性別混亂(e.g.A是B的媽媽,A是C的阿公)

  不用考慮以下幾種錯誤:

1.稱謂不一樣(e.g.A是B的哥哥,C是A的爸爸,C是B的叔叔)

2.有可能出現同性婚姻或一個人有多個伴侶

3.除輩分、年齡與性別混亂,其他一律不考慮

Input

第一行有兩數字N、M,代表有幾人與幾行輸入(0<N≦26,0<M≦30)

接著有M行,每行有兩字元C1、C2及一字串S,代表C1是C2的S

C1、C2為第一個(A)到第N個大寫字母。

S只可能為 : father、mother、parent、son、daughter、child、grandpa、grandma、grandparent、grandson、granddaughter、grandchild、older brother、older sister、younger brother、younger sister、brother、sister、cousin、uncle、aunt、nephew、niece、husband、wife

以上若有單字看不懂,請詢問google。

若沒指出性別(e.g.child、parent),則都有可能。

第一到第N個字母都一定會出現在輸入中至少一次,且全部人都會有關聯。(不會有人獨立和其他人沒關係,也不會有兩群彼此沒關聯)

Output

輸出有若干行,依序照輩分輸出,最大輩分的人輸出在第一行,第二大輩分的人輸出在第二行,以此類推。

每行依照年齡由大到小輸出,若年齡不一定,請參照上述規則第3點。

若輸入是錯誤的情況,請輸出,"DD被整了!"

Sample Input #1
4 3
A B father
C B brother
D B sister
Sample Output #1
A
D B C
Sample Input #2
6 5
A B mother 
B C sister
D E grandson
C D big brother
E F wife

Sample Output #2
E F
A
C D B
Sample Input #3
3 3
A B husband
B C child
C A grandson
Sample Output #3
DD被整了!
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (12%): 1.0s , <1K
公開 測資點#1 (12%): 1.0s , <1K
公開 測資點#2 (12%): 1.0s , <1K
公開 測資點#3 (15%): 1.0s , <1K
公開 測資點#4 (15%): 1.0s , <1K
公開 測資點#5 (15%): 1.0s , <1K
公開 測資點#6 (19%): 1.0s , <1K
Hint :

第一筆範例中:

A是B、C、D的爸爸

B、C、D三人不清出年齡,因此D為最大,接著以字母順序,B次之,C最小

第二筆範例中:

F、E是阿公阿嬤

A是媽媽

C是大哥,B、D年齡不清,依照規則D較大

Tags:
DD 拓樸排序
出處:
DD的奇幻冒險之旅 [管理者:
_xdddd ((找不到本用戶!))
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」