← 返回题目列表

Codeforces · 1458/B

B. 玻璃洒了一半

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

桌子上有 $$$n$$$ 个玻璃杯,编号为 $$$1、\ldots、n$$$。玻璃杯 $$$i$$$ 最多可容纳 $$$a_i$$$ 单位的水,目前包含 $$$b_i$$$ 单位的水。

您想要选择 $$$k$$$ 玻璃杯并在其中收集尽可能多的水。为此,您可以根据需要多次将水从一个玻璃杯倒入另一个玻璃杯中。然而,由于眼镜的笨拙形状(并且与您天生的笨拙完全无关),每次您尝试转移任何量的水时,一半的水都会洒在地板上。

正式来说,假设一杯 $$$i$$$ 目前包含 $$$c_i$$$ 单位的水,一杯 $$$j$$$ 包含 $$$c_j$$$ 单位的水。假设您尝试将 $$$x$$$ 单位从玻璃 $$$i$$$ 转移到玻璃 $$$j$$$(当然,$$$x$$$ 不能超过 $$$c_i$$$)。然后,$$$x / 2$$$ 单位洒在地板上。转移完成后,玻璃杯 $$$i$$$ 将包含 $$$c_i - x$$$ 个单位,玻璃杯 $$$j$$$ 将包含 $$$\min(a_j, c_j + x / 2)$$$ 个单位(玻璃杯装不下的多余水也会溢出)。

每次转水时,可以任意选择从哪个玻璃$$$i$$$倒到哪个玻璃$$$j$$$,且转水量$$$x$$$可以是任意正实数。

对于每个 $$$k = 1, \ldots, n$$$,确定在玻璃杯之间转移水零次或多次后,可以在任意选择的 $$$k$$$ 玻璃杯中收集到的最大可能的水总量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 眼镜的数量。

以下 $$$n$$$ 行描述了眼镜。这些行的第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$0 \leq b_i \leq a_i \leq 100$$$, $$$a_i > 0$$$) - 分别是玻璃 $$$i$$$ 的容量和当前包含的水量。

输出

打印 $$$n$$$ 实数 - 分别在 $$$1、\ldots、n$$$ 个玻璃杯中可以收集到的最大水量。如果每个数字在精确答案的 $$$10^{-9}$$$ 绝对或相对容差范围内,您的答案将被接受。

示例

输入 #1

3
6 5
6 5
10 2

输出 #1

7.0000000000 11.0000000000 12.0000000000

注意

在示例案例中,您可以执行以下操作:

- 对于 $$$k = 1$$$,将水从前两个玻璃杯转移到第三个玻璃杯,溢出 $$$(5 + 5) / 2 = 5$$$ 单位并固定 $$$2 + (5 + 5) / 2 = 7$$$ 单位;
- 对于 $$$k = 2$$$,将水从第三个玻璃杯转移到前两个玻璃杯中的任何一个,溢出 $$$2 / 2 = 1$$$ 单位并确保 $$$5 + 5 + 2 / 2 = 11$$$ 单位;
- 对于 $$$k = 3$$$,不执行任何操作。所有 $$$5 + 5 + 2 = 12$$$ 单位均已锁定。