0 Judge
Code: 0
有一天羅西斯(L C-S)的回家作業是要找兩個字串的最長共同子序列(LCS) 一個字串的子序列就是刪除一個字串中的一些字元後剩下的字串按照本來的相對順序接起來的字串們 例如字串 'ababc' 的子序列有 'ababc','abbc','abab','abc','ac','a','b','c','', ... , 而 'acb','aaa' 不是 'ababc' 的字序列 而兩個字串 A, B 共同字序列就是同時是 A 的子序列也是 B 的子序列的字串 例如 'abcd', 'dbca' 的共同字序列有 'bc','b', 'c',''
這個作業的分數會與羅西斯找到的字串長度有關 如過最長共同子序列長度是 d, 而羅西斯找到的長度是 t, 羅西斯得到的分數就是 100*t/d
羅西斯想到一個近似的作法
步驟 1: 設定 ans = 0 步驟 2: 如果 A, B 其中一個是空字串: 輸出 ans, 結束程式 步驟 3: 如果 A 的最後一個字元與 B 的最後一個字元相同: ans 增加一, 將 A 和 B 各自的最後一個字元刪除, 回到步驟 2 步驟 4: 丟一個公正的硬幣(正面反面出現的機率都是0.5) 如果是正面就移除 A 的最後一個字元, 否則移除 B 的最後一個字元, 回到步驟 2
作業成績出來後, 羅西斯發現他拿到了不錯的分數 (至少羅西斯是這麼認為的), 而你想要知道羅西斯到底是運氣好還是這個演算法真的很好, 所以你決定寫一個程式計算羅西斯的作法的分數的期望值。 分數的期望值 $E$ 的計算定義是, 對於所有可以出現的分數 $s_i$ 和這個分數出現的機率 $p_i$ 相乘後相加 也就是說 $ E = \sum s_i p_i $
輸入的第一行包含一個整數 $T(T\leq 10)$，代表接下來有 $T$ 個測試資料。每個測試資料包含兩行字串 A, B 長度都大於零 0 小於等於 500
如果原本字串的 LCS 長度為 0, 輸出 100 對於每筆測式資料，輸出一行，表示分數的期望值, 無條件捨去到個位數字
所有字串長度小於 10
無額外限制
如果用 LCS(n,m) 表示 A 的前 n 個字元與 B 的前 m 個字元的最長共同子序列長度 LCS(0,i) = 0, LCS(i,0) = 0 LCS(n,m) = max{ LCS(n-1,m), LCS(n,m-1), LCS(n-1,m-1) + (A[n] == B[n]) } LCS(n,m) = d