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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144
2 5000 65536 262144
3 5000 65536 262144
4 5000 65536 262144
5 5000 65536 262144
6 5000 65536 262144
7 5000 65536 262144
8 5000 65536 262144
9 5000 65536 262144