TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

94.4% (17/18)

Submission's AC Ratio

45.8% (22/48)

Description

  「非常紅娘」是某家電視公司即將開播的節目,每次只會有一位女主角參加,而男主角們必須通過女主角的層層考驗,最後留下來的那一位最佳男主角,可以和女主角共進燭光晚餐。「非常速配」視節目裡的一個單元,在這個單元中,將考驗著女主角與男主角們的默契!首先,女主角與男主角們各自寫下一個英文單字(最少三個字母,最多十五個字母的單字,字母全部小寫),然後將每位男主角的單字與女主角的單字各別進行「速配」,『速配程式』將替各位男主角算出與女主角的「速配指數」,這個單元需要找出速配指數最高的男主角,頒發一個「速配獎」。而你,受到節目製作人的邀約,將負責實作這一個『速配程式』。『速配程式』需要比對兩個單字的相似程度,我們將舉例說明相似程度的計算方式。

  在比較單字時我們會對每個位置去比較字母相不相同,若字母相同我們會給1分;若字母不同我們會扣0.5分;若字母對到空白,會扣0.3分;空白對到空白則不給分。最後將每個位置的分數相加,即代表這兩個單字的『速配分數』(與速配指數不同)。在下面的圖例中,空白將以□來表示。

  如此一來,不同的對齊方法,會產生不同的結果。且對齊的方法也有無限多種。每種對齊的方法都有一個「速配分數」。而「速配指數」=最大的「速配分數」除以女主角的單字長度×100%。注意:「速配分數」與「速配指數」並不相同喔!

例一:aspire(女主角的單字)與aspect(男主角的單字)的速配指數為何?

下面舉三個例子說明如何計算速配分數:

  • 第一種對齊方法(這是分數最高的方法之一):

  •  
     速配分數 = 1+1+1-0.3-0.3+1-0.3-0.3 = 2.8 分

  • 第二種對齊方法:

  •  
     速配分數 = 1+1+1-0.5-0.5-0.5 = 1.5 分

  • 第三種對齊方法:

  •  
     速配分數 = -0.3-0.5-0.3+1-0.3-0.5-0.3-0.3-0.3 = -1.8 分

以上只列舉三種方法,尚有其他可能的對齊方法需全部考慮。
所以 aspire 跟 aspect的「速配指數」=(所有aspire與aspect的對齊方法中最高的「速配分數」)÷6(女主角的單字長度)×100% = 2.8÷6×100% = 46.6666%
例二:combine(女主角所寫單字)與cancel(男主角所寫單字)的速配指數為何?
下面舉三個例子說明如何計算速配分數:

  • 第一種對齊方法:

  •  
     速配分數 = 1-0.5-0.5-0.3-0.3-0.5+1-0.3 = -0.4 分

  • 第二種對齊方法(這是分數最高的方法之一):

  •  
     速配分數 = 1-0.3-0.3-0.3-0.5+1-0.3+1-0.3 = 1 分

  • 第三種對齊方法:

  •  
     速配分數 = 1-0.5-0.5-0.5-0.5-0.5-0.3 = -1.8 分

以上只列舉三種方法,尚有其他可能的對齊方法需全部考慮。
所以 combine 跟 cancel的「速配指數」=(所有combine與cancel的對齊方法中最高的「速配分數」)÷7(女主角的單字長度)×100% = 1÷7×100% = 14.2857%

條件限制:

  1. 速配指數不限定為正數,也有可能是負數。

  2. 輸入的單字長度最少三個字母,最多十五個字母。

Input Format

輸入檔可能包含多筆測試資料,我們保證TIOJ輸入的測試資料數量不會超過51,000組。
每筆測試資料佔兩列,第一列包含一個英文單字,代表女主角所寫下的單字。
第二列包含一個英文單字,代表男主角所寫下的單字。

Output Format

對每一筆測試資料,請輸出「速配指數」至小數第二位。

Sample Input

aspire
aspect
combine
cancel

Sample Output

46.67%
14.29%

Hints

※因為空白小方格打不出來,所以用星號代替,大家看得懂就好~

※2007/11/12:範例輸出錯誤,感謝stimim!

Problem Source

原TIOJ1118 / 92北市賽(prob 4)。Special thanks:kelvin。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536