在创建高负载系统时,应特别注意缓存。这个问题将涉及一种最流行的缓存算法,称为 LRU(最近最少使用)。
假设缓存可以存储不超过 k 个对象。在工作流程开始时,缓存为空。当查询某个对象时,我们检查它是否存在于缓存中,如果不存在则将其移至此处。如果在此之后缓存中有超过 k 个对象,则应删除最近最少使用的对象。换句话说,我们删除上次查询时间最小的对象。
考虑服务器上存储了 n 个视频,所有视频的大小都相同。缓存最多可以存储k个视频,并且应用上述缓存算法。我们知道,每当用户进入服务器时,他都会以概率 pi 选择视频 i。视频的选择与之前的任何事件无关。
此问题的目标是计算每个视频在 10100 次查询后出现在缓存中的概率。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 20) - 分别是视频数量和缓存大小。下一行包含 n 个实数 pi (0 ≤ pi ≤ 1),每个实数小数点后不超过两位。
保证所有 pi 之和等于 1。
输出
打印n个实数,其中第i个应该等于第i个视频在10100次查询后出现在缓存中的概率。如果绝对或相对误差不超过 10 - 6,您的答案将被视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
3 1 0.3 0.2 0.5
输出 #1
0.3 0.2 0.5
输入 #2
2 1 0.0 1.0
输出 #2
0.0 1.0
输入 #3
3 2 0.3 0.2 0.5
输出 #3
0.675 0.4857142857142857 0.8392857142857143
输入#4
3 3 0.2 0.3 0.5
输出#4
1.0 1.0 1.0