题目背景

由于洛谷测试点大小限制，剩余数据可在此题评测

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <vector>

int count(std::vector<int> P);

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2「 마법 구슬 찾기」

题目描述

你有 $k+1$ 颗外观和质量完全相同的珠子，其中 $k$ 颗是普通珠子，$1$ 颗是魔法珠子。你需要找到这颗魔法珠子，才能进入魔法城堡。

虽然无法通过肉眼区分魔法珠子和普通珠子，但你可以使用 $M (M \geq 2)$ 个袋子来找到魔法珠子。袋子编号从 $0$ 到 $M-1$。

找到魔法珠子的步骤如下：

1. 将所有珠子分装到 $M$ 个袋子中。
   • 每个袋子里必须有珠子，不能有空袋子。
   • 袋子里只能装珠子，不能装其他袋子。
2. 念咒语。
3. 念咒语后：
   • 不含魔法珠子的袋子里的珠子会全部消失。
   • 含有魔法珠子的袋子里的珠子会因为魔法珠子的保护而不消失，但需要支付费用。若魔法珠子在第 $i$ 个袋子中，且该袋子里有 $j$ 颗珠子，则费用为 $A[i] \times j + B[i] (A[i] \geq 0, B[i] \geq 1)$ 元。

魔法珠子永远不会消失，因此你可以重复上述步骤，直到只剩下魔法珠子。

你需要制定一个策略，将珠子分装到袋子中，以最小化在最坏情况下找到魔法珠子的费用。也就是说，无论哪颗珠子是魔法珠子，总费用不超过 $w$ 元，找出最小的 $w$。

请编写一个函数，解决 $0$ 到 $N-1$ 的所有 $k$ 的问题。

你需要实现以下函数：

vector<long long> find_minimum_costs(int N, vector<int> A, vector<int> B);

• N：珠子的最大数量
• A, B：长度为 $M$ 的数组。对于每个 $i (0 \leq i \leq M-1)$，若魔法珠子在第 $i$ 个袋子中，且该袋子里有 $j$ 颗珠子，则费用为 $A[i] \times j + B[i]$ 元。
• 该函数返回一个长度为 $N$ 的数组 $C$。对于每个 $k (0 \leq k \leq N-1)$，$C[k]$ 是在有 $k$ 颗普通珠子和 $1$ 颗魔法珠子的情况下，找到魔法珠子的最坏情况下的最小费用（单位：元）。

注意，提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N\,M$
• 第 $2+i (0 \leq i \leq M-1)$ 行：$A[i]\,B[i]$

输出格式

示例评测程序的输出格式如下：

• 第 $1+k (0 \leq k \leq N-1)$ 行：$C[k]$

3 2
1 2
3 1

0
4
8

13 2
1 2
3 1

0
4
8
11
13
17
18
20
24
25
27
29
30

12 3
5 1
3 4
0 6

0
6
7
12
13
16
17
18
19
20
22
23

提示

样例解释 #1

考虑 $N=3, M=2, A=[1,3], B=[2,1]$ 的情况。

评测程序将调用如下函数：

find_minimum_costs(3, {1,3}, {2,1});

当 $k=0$ 时，只有一颗珠子，即魔法珠子，因此费用为 $0$ 元。

当 $k=1$ 时，可以将两颗珠子分别放入两个袋子。若魔法珠子在第 $0$ 个袋子中，费用为 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元；若魔法珠子在第 $1$ 个袋子中，费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元。因此，最坏情况下费用为 $4$ 元。

当 $k=2$ 时，可以采用以下策略。假设三颗珠子分别为 $X, Y, Z$。

• 将 $X$ 和 $Z$ 放入第 $0$ 个袋子，将 $Y$ 放入第 $1$ 个袋子，然后念咒语。
• 若魔法珠子在第 $0$ 个袋子中，费用为 $A[0] \times 2 + B[0] = 1 \times 2 + 2 = 4$ 元，剩下 $X$ 和 $Z$。然后将 $Z$ 放入第 $0$ 个袋子，将 $X$ 放入第 $1$ 个袋子，再次念咒语。
  • 若魔法珠子在第 $0$ 个袋子中，费用为 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元，剩下 $Z$。
  • 若魔法珠子在第 $1$ 个袋子中，费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元，剩下 $X$。
• 若魔法珠子在第 $1$ 个袋子中，费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元，剩下 $Y$。

在这种策略下，若 $X$ 是魔法珠子，总费用为 $4 + 4 = 8$ 元；若 $Y$ 是魔法珠子，总费用为 $4$ 元；若 $Z$ 是魔法珠子，总费用为 $4 + 3 = 7$ 元。因此，最坏情况下费用为 $8$ 元。

函数应返回 [0,4,8]。