TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

77.8% (7/9)

Description

全台離婚率逐年攀升,台北市晚晴協會觀察,結婚未滿2年與超過20年以上配偶呈現「離婚雙高峰」,顛覆傳統「七年之癢」說法。而在法律求助上,孩子監護權改定需要增高,協會呼籲要離婚的父母重視小孩的感受,別拿孩子當作懲罰對方的工具。

平均每100人7人離婚

行政院主計處統計,全台離婚率從2004年的5.47%逐年上升,去年已高達6.63%,將近每100人就有7人離婚。晚晴協會分析諮詢個案發現,「配偶外遇、個性不合與婚姻暴力」仍占婚姻問題的前3名,有4成面臨外遇,且女性隨工作機會增加,面臨外遇,爭取權益與求助的比例也增加一成。(From 自由時報電子報)

然而,如果能事先算出雙方的契合度,以此決定要不要結婚就可以有效避免離婚的問題。

經過研究,科學家發明了一個方法:

1.請男女雙方在腦中思念對方的同時在不同紙上各寫下一串字

2.滿懷誠意的將兩個人的紙交換

3.把對方紙上字串中看起來不順眼的字塗掉

4.令兩個字串的長度分別為La, Lb

5.計算現在兩張紙上字串的Edit Distance,令之為k

6.得契合度為 (La+Lb)/2 - (La+Lb+7)k - ( 11*Max(La,Lb)-11*Min(La,Lb)-7 )/7

現在你已經知道雙方一開始寫在紙上的字,

請問這對情侶契合度最大是多少?請四捨五入至整數位

Input Format

輸入有兩行,分別代表兩個人一開始在紙上寫的字串。

兩個字串長度分別不超過50,000個字元,且我們保證出現的每個字元都是可見字元,即ASCII值皆>=32(不然有寫等於沒寫)。

Output Format

一個整數,代表他們最大可以達到的契合度。

Sample Input

ab
ba

Sample Output

1

Hints

註:此題中 Edit Distance 的定義為: 一個字串需要幾次的插入/刪除字元動作方能成為另一個字串

※2009/02/28:Tmt補測資範圍,有需要請自行更改。
※2009/03/01:補上數據範圍 - skyly

Problem Source

原TIOJ1517 / Problem Setter: shik

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10