TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3736
  • 题目
  • P3736彩虹小马与魔法盒子
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

    云宝黛西梦想能加入闪电飞马队,但她如果想要在飞驰中控制天气,就必须加快自己飞行的速度,而那样可能产生彩虹音爆而误伤队友,这显然是她不愿意看到的。于是她只好将各种天气存入一个魔法盒子,在需要使用时取出。当她需要使用某种天气魔法时,如果这种天气已经储存在魔法盒子中,她就可以直接使用;而如果这种天气没有被储存,她就不得不将其存入魔法盒子后再使用——而如果这时魔法盒子已经被装满,她就会将最近一次使用时间离现在最久的天气取出,再存入此时需要使用的天气。因为她正在为加入闪电飞马队筹划着,所以她想要知道很久以后哪些天气可能存在于魔法盒子中。于是她来请求你的帮助,请你帮她算出在使用了10^100次天气魔法后,每种天气存在于魔法盒子的概率。

    输入格式

    第一行,两个整数n,k分别表示天气魔法的数量和魔法盒子的容量。
    第二行,用空格间隔的n个实数p1~pn,pi表示需要使用第i种天气魔法的概率。

    输出格式


    用空格间隔的n个实数,分别表示云宝黛西使用了10^100次天气魔法后,第1种~第n种天气存在于魔法盒子中的概率(全部保留4位小数)。

    样例输入 1

    3 1
    0.3 0.2 0.5

    样例输出 1

    0.3000 0.2000 0.5000

    样例输入 2

    3 2
    0.3 0.2 0.5

    样例输出 2

    0.6750 0.4857 0.8393

    提示

    1<=k<=n<=20
    0<=pi<=1
    数据保证概率pi之和为1


    来源  来自Codeforces,由Cyalanthus篡改语种,篡改题目描述,篡改输出格式。