Skip to content

1434: Fair division

题目

题目描述

你——伟大的赏金猎人,经过了史诗般的战斗后,夺取了属于你的战利品——一个重量为 $w$ 克的金块。

你的 $n$ 个扈从功不可没。根据每个人自己汇报的功劳大小,你决定给第 $i$ 个扈从 $a_i$ 重量的金块,其中 $\sum_i a_i = w$。

在以枪火为筹码谈生意的的比尔吉沃特,没有人做慈善。如果你请比港商行老板帮你分金块,你需要足额支付手续费。如果一个金块在切割前重量为 $x$,你需要为这次分割付出 $x \times p \\%$ 枚的银蛇币,之后金块可以以任意比例被切为两块。

你需要在满足所有扈从的要求的情况下,支付尽可能少的银蛇币。由于银蛇币不可分割,你只需要在最后一次性支付所有切割代价的和向上取整枚银蛇币即可。

Input

请从 stdin 读入。

第一行三个整数 $n, w, p\,(1 \leq n \leq 10 ^ 5, 0 \leq w \leq 10 ^ 7, 0 < p < 100)$,分别表示人数、金块重量、与手续费百分比。

第二行 $n$ 个空格隔开的正整数,第 $i$ 个为第 $i$ 个人需求的重量 $a_i\,(a_i \geq 1, \sum_i a_i = w)$。

对于 $30$ 分的数据,$n \leq 15$。

Output

请输出到 stdout 中。

输出一行一个整数,表示答案。

Sample Input

1 1 1 1 3 3 50 1 1 1 3 7 50 4 2 1

Sample Output

0 3 5

Note

三组样例精确答案分别是 $0, 2.5, 5$。

请注意,如果你想使用浮点数计算,请尽可能使用 double 而不是 float,后者只有 24 bit 有效数字。

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!