回分類題庫
d306: (1052cp2_assignment3) Stable Relationship Problem
出處:

Difficulity : 3
Accepted : 56 Times | Submit :561 Times | Clicks : 2032
Accepted : 31 Users | Submit : 56 Users | Accepted rate : 55%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2017-03-29 09:25

Content :

大學畢修三學分學業、愛情、社團,愛情常常是帶給我們最多卻也同時傷我們最深的,請試著設計一個配對系統,讓尋求配對的男性與女性達到一個一對一的穩定關係狀態,讓他們能夠一直相愛下去。
 
每個人都會說出他的性別、選擇伴侶的三個條件以及數個個人條件的量化數值,透過自己的條件偏好與其他人的條件量化數值讓他們能夠知道自己比較喜歡誰,藉由這個關係能讓我們決定誰要幫誰配對。
 
穩定的關係為不穩定的關係相反,不穩定的關係定義:
已經和不同人在一起的 A 男與 B 女
A 男對 B 女說:我愛你比愛我女朋友還深
同時,B 女對 A 男說:我愛你比愛我男朋友還深
此時 A 男與 B 女會放棄原本的伴侶並在一起 
 
此問題已被證明有最佳解,請回答女性最佳解與男性最佳解兩個解
 
女性最佳解:從女性觀點出發,女性能夠跟比較喜歡的對象在一起 
男性最佳解:從男性觀點出發,男性能夠跟比較喜歡的對象在一起
 

Input :

每筆測資會有 N 個人 , N%2 == 0, 4 <= N <= 30
姓名:字串,0 < Len(Name) <= 10,姓名不會重複,名字間不會有空格 
性別: Male or Female, 男女人數會相等
偏好的條件:3 個,依序為最重視、次重視、些微重視
所有條件:M 個, 3 <= M <= 20,在同一輪配對中 M 會相同,條件名稱最多20個字元
條件量化數值:0 <= X <= 100 , X ∈ Integer
透過偏好條件決定喜好順序時,若同分則透過下一個偏好的條件決定順序,不會有透過三個偏好條件排序後仍同分的狀況

Output :

女性、男性最佳解:
該性別為首

配對排列順序:
為首的姓名字典排序法 (Wiki)

Sample Input :

4
H
Male
charm time affluence
time 50 intelligence 80 charm 90 talent 30 honesty 50 affluence 80
He
Male
affluence intelligence charm
talent 80 honesty 70 affluence 80 time 60 intelligence 90 charm 40
Do
Female
time charm talent
intelligence 50 charm 40 honesty 70 affluence 70 talent 80 time 30
Re
Female
honesty talent intelligence
charm 30 talent 60 honesty 80 affluence 70 time 60 intelligence 90

Sample Output :

For women:
Do + H
Re + He

For men:
H + Do
He + Re

Hint :


  

Author :

(管理員:cp2ta)

  Solve it!   Status Forum (0)

C++
C
JAVA
86294. nccucs105703030 (8 ms , 248KB)
86293. nccucs105703030 (8 ms , 246KB)
84265. nccucs105703036 (8 ms , 283KB)
83414. nccucs105703005 (8 ms , 248KB)
83306. cp2ta (8 ms , 304KB)
82875. nccucs101701042 (4 ms , 303KB)
84246. nccucs105703004 (5 ms , 246KB)
84218. nccucs105703010 (5 ms , 271KB)
86290. nccucs105703013 (6 ms , 261KB)
84191. nccucs105703039 (6 ms , 441KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡