← 返回题目列表

Codeforces · 109/B

B. 幸运概率

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

Petya 喜欢幸运数字。我们都知道,幸运数字是十进制表示中仅包含幸运数字4和7的正整数。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。

Petya 和他的朋友 Vasya 玩一个有趣的游戏。 Petya 从区间 [pl, pr] 中随机选择一个整数 p,Vasya 从区间 [vl, vr] 中选择一个整数 v(也是随机的)。两个玩家等概率地选择他们的整数。求区间 [min(v, p), max(v, p)] 恰好包含 k 个幸运数字的概率。

输入

单行包含五个整数 pl、pr、vl、vr 和 k (1 ≤ pl ≤ pr ≤ 109、1 ≤ vl ≤ vr ≤ 109、1 ≤ k ≤ 1000)。

输出

在单行上打印结果,绝对误差不超过 10 - 9。

示例

输入 #1

1 10 1 10 2

输出 #1

0.320000000000

输入 #2

5 6 8 10 1

输出 #2

1.000000000000

注意

考虑[a, b]表示整数区间;该区间包括边界。即 $$\left[a,b\right] \stackrel{\mathrm{def}}{=}\{x\in\mathbb{R}:a\leqslant x\leqslant b\}$$

在第一种情况下,有 32 个合适的对: (1, 7), (1, 8), (1, 9), (1, 10), (2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10), (4, 7), (4, 8), (4, 9), (4, 10), (7, 1), (7, 2), (7, 3), (7, 4), (8, 1), (8, 2), (8, 3), (8, 4), (9, 1), (9, 2), (9, 3), (9, 4), (10, 1), (10, 2), (10, 3), (10, 4)。可能的对总数为 10·10 = 100,因此答案为 32 / 100。

在第二种情况下,Petya 总是得到小于 Vasya 的数字,并且唯一的幸运数字 7 位于这些数字之间,因此总会有 1 个幸运数字。