题目描述

共有 $n$ 种配料，按照在商品中所占百分比从高到低排列。

设第 $i$ 种配料所占百分比为 $a_i$，则必须满足：

并且

部分配料的百分比已经在标签上给出，其余配料的百分比未知。

对于每一种百分比未知的配料，请分别求出：

• 它在所有合法方案中的最小可能百分比；
• 它在所有合法方案中的最大可能百分比。

每一种配料的最小值和最大值可以分别由不同的合法方案取得。

输入格式

第一行输入一个整数 $n$，表示配料数量。

接下来 $n$ 行按照标签中的顺序描述各项配料。每行包含：

• 一个字符串 $w$，表示配料名称；
• 其后可能还有一个实数 $p$，表示标签上给出的百分比。

若一行只有配料名称，则该配料的百分比未指定。

输出格式

按照输入中的出现顺序，仅输出百分比未指定的配料。

对于每一种这样的配料，输出一行三个字段：

配料名称 最小可能百分比 最大可能百分比

答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

在 Hydro OJ 中应使用支持绝对误差或相对误差比较的浮点数检查器。

数据范围

对于全部数据：

• $1\le n\le 100$；
• $1\le |w|\le 20$；
• 配料名称互不相同，且仅包含小写英文字母 a 到 z；
• 已给出的百分比满足 $0<p\le 100$；
• 输入中的百分比至多包含一位小数；
• 至少有一种配料的百分比未指定；
• 输入保证至少存在一种满足全部条件的合法百分比分配方案。

样例 1

6
chocolate 41.1
sugar
peanuts 20
starch
thickener
glaze

sugar 20 38.9
starch 0 18.9
thickener 0 9.45
glaze 0 6.3

样例 2

1
water

water 100 100

样例 3

4
flour
milk
egg
salt

flour 25 100
milk 0 50
egg 0 33.33333333
salt 0 25

时间与空间限制

• 时间限制：$1\text{ s}$
• 空间限制：原题面未注明，导入 Hydro OJ 时可按平台默认值设置

难度评定

CF 2300。 需要在单调约束与总和约束下分别求每个未知变量的可行极值，并证明构造出的上下界确实可达；连续值与精度处理也增加了实现难度。