1517 . Problem G. 我們(不)結婚，好嗎?
TopCoder
Tags
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 1
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 |