← 返回题目列表

Codeforces · 248/E

E. 小猪的生日

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

小猪今天过生日。他的朋友小熊维尼想为他做最好的礼物——蜜罐。当然,温妮意识到他无法将全部彩池交给小猪。事实上,他很可能把罐子里的蜂蜜都吃光了。当温妮计划好要吃零食时,锅里首先应该有尽可能多的蜂蜜。

小熊维尼补充蜂蜜库存的前一天。小熊维尼家里有n个架子,每个架子上有一些,也许是零个蜜罐。白天,温妮来到蜂蜜货架q次;第 i 次,他来到某个架子 ui 处,从中取出一些罐子 ki,尝了每个罐子里的蜂蜜,然后将所有这些罐子放在某个架子 vi 上。温尼选择花盆时,他遵循自己的直觉。这意味着在架子 ui 上的所有 ki 罐组中,他等概率地选择一个。

现在温妮记得他用蜜罐进行的所有动作。他想带着前一天没有尝试过的壶去参加聚会。为此,他必须知道没有一个未尝过的锅的架子数量 m 的数学期望。为了更好地评估他的机会,小熊维尼想知道他执行每个动作后的值 m。

你的任务是编写一个程序来为他找到这些值。

输入

输入的第一行包含一个数字 n (1 ≤ n ≤ 105) — Winnie 所在位置的货架数量。第二行包含 n 个整数 ai (1 ≤ i ≤ n, 0 ≤ ai ≤ 100) — 第 i 号货架上的蜜罐数量。

下一行包含整数 q (1 ≤ q ≤ 105) — 温妮前一天执行的操作数。然后是 q 行,其中第 i 行描述了按时间顺序发生的事件;该行包含三个整数 ui、vi 和 ki (1 ≤ ui, vi ≤ n, 1 ≤ ki ≤ 5)——Winnie 拿走罐子的架子编号,Winnie 品尝完每个罐子后将罐子放在架子上的编号,以及 Winnie 相应品尝的罐子数量。

考虑带有编号为 1 到 n 的整数的盆的架子。可以保证的是,小熊维尼从来没有尝试过从架子上拿走比它现有的更多的罐子。

输出

对于每个 Winnie 的动作,打印执行该动作时的数学期望 m 的值。每个值的相对或绝对误差不得超过10 - 9。

示例

输入 #1

3
2 2 3
5
1 2 1
2 1 2
1 2 2
3 1 1
3 2 2

输出 #1

0.000000000000
0.333333333333
1.000000000000
1.000000000000
2.000000000000