← 返回题目列表

Codeforces · 698/C

C. 最近最少使用

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

在创建高负载系统时,应特别注意缓存。这个问题将涉及一种最流行的缓存算法,称为 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