問題文
高桥喜欢未雕刻的键盘。 今天,我尝试在键帽上只写有字母和数字的键盘上书写。
然而,高桥并不完全记住键盘布局。 如果你记住了某个字符的按键,你可以直接敲击该字符对应的按键,但如果你不记得这个字符,你就必须随机选择它并敲击它,如果你犯了错误,你必须用退格键将其删除。
高桥君正在写 S 。我想尽可能减少输入这句话的预期击键次数。高桥能够记住按下某个键时会出现哪个字符,并根据该信息选择下一步要按哪个键。
当高桥采用最优策略来实现上述目标时,预期的击键次数是多少?
假设您记住退格键以及除字母和数字之外的所有键的位置。
此外,不允许进行更改输入位置的操作,例如箭头键或鼠标操作。 在
入力
输入是按以下格式从标准输入给出的。
S K
- 1 行中,输入要输入的字符串。 S (1 ≦ |S| ≦ 50) 是 在1 行中给出。字符串 S 保证仅包含小写字母或数字。
- 2 行包含一个字符串,表示 Takahashi 记住的密钥类型。
来自 K 是
在1 行中给出。字符串 K 是
1234567890abcdefghijklmnopqrstuvwxyz,1 可以通过多次选择和删除一个字符来创建的字符串。1有保证。 如果您正确回答了满足
出力
高桥需要击键的次数的期望值为 输出为 1 行。在输出末尾添加换行符。
输出存在绝对或相对误差。 10^{-6} 或更少是可以接受的。
入力例1
takahashikun 1234567890abcdefghijklmnopqrstuvwxyz
出力例1
12
高桥记得所有的钥匙。
因此,您必须按该键的次数为
与takahashikun 中的字符数相同 12 次。
入力例2
p 1234567890abcdefghijklmnorstuvwxyz
出力例2
2
高桥君,p和q的 2 我丢失了一把钥匙。
为了输入
p,我不明白这一点 2 两个键之一 1 您必须按一。
当你按下
p时,句子就完成了,所以高桥按下的键总数是 当您按 1 。q时, 1 键是 事实证明p。因此,退格键 1 删除字符并重试 按p键完成句子。此时高桥按下按键的次数是 3 次。
由于以上按键被选择的概率相等,因此按键次数的期望值为 2 。