CF1121C System Testing

Vasya 喜欢参加 Codeforces 比赛。当一轮比赛结束后，Vasya 会在系统测试标签页关注所有提交。 共有 $n$ 个提交，第 $i$ 个提交需要在 $a_i$ 个测试点上进行测试，测试一个提交在一个测试点上需要 $1$ 秒。提交会按照 $1$ 到 $n$ 的顺序依次被判题。有 $k$ 个测试进程可以同时测试提交。每个进程同一时刻最多只能测试一个提交。 在任意时刻 $t$，如果某个测试进程没有正在判题，它会从队列中取出第一个提交，并按照测试点编号递增的顺序依次测试。假设该提交编号为 $i$，那么它会从时刻 $t$ 开始在第一个测试点上测试至 $t+1$，然后在第二个测试点上测试至 $t+2$，以此类推。该提交会在时刻 $t+a_i$ 完成所有测试，之后该测试进程会立即开始测试下一个提交。 在任意时刻，假设已经有 $m$ 个提交全部测试完成。此时页面上会显示 “System testing: $d$ %”，其中 $d$ 的计算方式为 $$ d = round\left(100 \cdot \frac{m}{n}\right) $$ 其中 $round(x) = \lfloor x + 0.5 \rfloor$，即将实数四舍五入到最接近的整数。 Vasya 称一个提交为“有趣的”，如果存在某一时刻（可以不是整数时刻），该提交正在某个测试点 $q$ 上被测试，并且页面上显示的进度为 “System testing: $q$ %”。请你计算有多少个有趣的提交。 请注意，如果有多个进程在同一时刻尝试取队列中的第一个提交（例如在初始时刻），它们取提交的顺序无关紧要。

第一行包含两个正整数 $n$ 和 $k$（$1 \le n \le 1000$，$1 \le k \le 100$），分别表示提交数量和测试进程数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 150$），其中 $a_i$ 表示第 $i$ 个提交需要测试的测试点数量。

输出一个整数，表示有趣的提交数量。

考虑第一个样例。在时刻 $0$，两个提交同时开始测试。在时刻 $49$，第一个提交全部测试完成，因此在时刻 $49.5$，第二个提交正在第 $50$ 个测试点上被测试，此时页面显示 “System testing: 50 %”（因为两个提交中有一个已完成）。所以第二个提交是有趣的。 再看第二个样例。在时刻 $0$，第一个和第二个提交同时开始测试。在时刻 $32$，第一个提交全部测试完成，第三个提交开始测试，此时页面显示 “System testing: 25 %”。在时刻 $32 + 24.5 = 56.5$，第三个提交正在第 $25$ 个测试点上被测试，页面显示进度仍为 “System testing: 25 %”，因此该提交是有趣的。之后第三个提交在时刻 $32 + 33 = 65$ 完成全部测试，第四个提交在时刻 $65 + 1 = 66$ 完成。页面进度变为 “System testing: 75 %”，在时刻 $74.5$，第二个提交正在第 $75$ 个测试点上被测试。所以该提交也是有趣的。总共有两个有趣的提交。 由 ChatGPT 4.1 翻译