[ICPC2016 WF] Balanced Diet

## 题目描述 每天，Danny 都会从糖果店买一颗糖并吃掉它。糖果店中有 $m$ 种糖，编号为 $1 \dots m$ 。 Danny 知道均衡饮食很重要，他正在尝试在购买糖果时有一个均衡的饮食。因此他给每种糖 $i$ 分配了一个目标分数 $f_i (0 \le f_i \le 1, f_i$ 为一个实数 $) $, 。他希望他所吃的所有糖中，第 $i$ 种糖的数量占比大概为 $f_i$ 。 准确的说， 令 $s_ i$ 表示 Danny 已经吃掉的第 $i$ 种糖的数量, $n = \sum _{i=1}^ m s_ i$, 我们认为一种吃糖的方法是均衡的仅当对于所有的 $i$，满足： $$n f_ i - 1 < s_ i < n f_ i + 1$$ Danny 已经购买并吃掉了一些糖，并且他保证每个前缀的饮食都是均衡的。他想知道在保证每个前缀均衡饮食的条件下，他最多还能吃多少颗糖。 给定目标分数 $f_i$ 和他已经吃过的糖果序列，请你确定在保证每个前缀均衡饮食的条件下，Danny 最多还能购买并吃掉多少颗糖果。 ## 输入格式 输入包含三行。第一行包括两个整数 m $1 \le m \le 10^5$ 表示糖果的种类, $k(0 \le k \le 10^5)$ 表示 Danny 已经吃掉的糖果数量。 第二行包括 $m$ 个正整数 $a_1 \dots a_m$, 有 $ \displaystyle f_ i = \frac{a_ i}{\sum _{j = 1}^ m a_ j}$, 保证 $\sum_{i=1}^m a_i \le 10^5$ 。 第三行包括 $k$ 个正整数 $b_1 \dots b_k (1 \le b_i \le m)$, 表示 Danny 在第 $i$ 天购买并吃掉的糖的种类。保证序列的每个前缀（包括整个序列）是饮食均衡的。 ## 输出格式 输出在保证每个前缀饮食均衡的条件下，Danny 最多还能购买并吃掉多少颗糖。 如果糖果的数量没有上限（即 Danny 能一直买下去），输出 `forever`。

Every day, Danny buys one sweet from the candy store and eats it. The store has $m$ types of sweets, numbered from $1$ to $m$. Danny knows that a balanced diet is important and is applying this concept to his sweet purchasing. To each sweet type $i$, he has assigned a target fraction, which is a real number $f_ i$ ($0 < f_ i \le 1$). He wants the fraction of sweets of type $i$ among all sweets he has eaten to be roughly equal to $f_ i$. To be more precise, let $s_ i$ denote the number of sweets of type $i$ that Danny has eaten, and let $n = \sum _{i=1}^ m s_ i$. We say the set of sweets is balanced if for every $i$ we have \[ n f_ i - 1 < s_ i < n f_ i + 1. \] Danny has been buying and eating sweets for a while and during this entire time the set of sweets has been balanced. He is now wondering how many more sweets he can buy while still fulfilling this condition. Given the target fractions $f_ i$ and the sequence of sweets he has eaten so far, determine how many more sweets he can buy and eat so that at any time the set of sweets is balanced.

The input consists of three lines. The first line contains two integers $m$ ($1 \le m \le 10^5$), which is the number of types of sweets, and $k$ ($0 \le k \le 10^5$), which is the number of sweets Danny has already eaten. The second line contains $m$ positive integers $a_1, \ldots , a_ m$. These numbers are proportional to $f_1, \ldots , f_ m$, that is, $\displaystyle f_ i = \frac{a_ i}{\sum _{j = 1}^ m a_ j}$. It is guaranteed that the sum of all $a_ j$ is no larger than $10^5$. The third line contains $k$ integers $b_1, \ldots , b_ k$ ($1 \le b_ i \le m$), where each $b_ i$ denotes the type of sweet Danny bought and ate on the $i^\text {th}$ day. It is guaranteed that every prefix of this sequence (including the whole sequence) is balanced.

Display the maximum number of additional sweets that Danny can buy and eat while keeping his diet continuously balanced. If there is no upper limit on the number of sweets, display the word forever.

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

1

6 4
2 1 6 3 5 3
1 2 5 3

forever

Time limit: 2000 ms, Memory limit: 1048576 kB. International Collegiate Programming Contest (ACM-ICPC) World Finals 2016