← 返回题目列表

AtCoder · code_formula_2014_qualA_d

D. 未刻键盘

中文机器翻译题面 查看原题

問題文

高桥喜欢未雕刻的键盘。 今天,我尝试在键帽上只写有字母和数字的键盘上书写。

然而,高桥并不完全记住键盘布局。 如果你记住了某个字符的按键,你可以直接敲击该字符对应的按键,但如果你不记得这个字符,你就必须随机选择它并敲击它,如果你犯了错误,你必须用退格键将其删除。

高桥君正在写 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 。