Magic Bead Discovery

You are given k+1 beads that look identical and have the same mass. Among them, k are ordinary beads and one is a magic bead. You must find the magic bead to enter the magical castle.

You cannot tell the magic bead apart by appearance, but you are allowed to use M (M \ge 2) bags labelled from 0 to M-1. The procedure to find the magic bead is as follows:

1. Distribute all the beads into the M bags such that each bag gets at least one bead. (Each bag must be non-empty and may contain only beads.)
2. Chant the magic spell.
3. After chanting:
   • All beads in any bag that does not contain the magic bead will vanish.
   • The bag containing the magic bead will keep its beads (thanks to the magic bead’s protection) but you have to pay a fee. If the magic bead is in bag i and that bag contains j beads, then the fee is $$A[i]\times j + B[i]$$ where \(A[i]\ge 0\) and \(B[i]\ge 1\).

Since the magic bead never vanishes, you can repeat the above steps until only the magic bead remains. Your goal is to devise a strategy for the distribution of beads (possibly over several rounds) so that the worst‐case total fee (in yuan) is minimized. In other words, no matter which bead is the magic bead, the total fee you pay does not exceed \(w\); you have to determine the minimum such \(w\).

You need to solve the problem for all scenarios where the number of ordinary beads k ranges from 0 to N-1 (recall that there is always one magic bead, so the total number of beads is \(k+1\)).

You are required to implement the following function:

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

Here,

• N is the maximum number of ordinary beads (i.e. you must solve for \(k = 0, 1, \dots, N-1\)).
• A and B are arrays of length M (with \(M \ge 2\)). For each bag \(i\) (\(0 \le i \le M-1\)), if the magic bead is in bag i and the bag contains j beads, then the fee is $$A[i]\times j + B[i].$$

The function should return an array C of length N, where for each k (\(0 \le k \le N-1\)), C[k] is the minimum possible worst-case total fee (in yuan) needed to eventually isolate the magic bead when starting with k ordinary beads and one magic bead.

Note: Your submitted code should not contain any input/output operations.

inputFormat

The function find_minimum_costs will be called with the following parameters:

• int N: the maximum number of ordinary beads (you must output results for k = 0, 1, …, N-1).
• vector<int> A and vector<int> B: arrays of length M (with M \ge 2), where for bag i the cost if it contains j beads is given by $$A[i]\times j + B[i].$$

Important: In each round you must distribute all the beads (totaling k+1 beads when there are k ordinary beads) into all M bags, with each bag receiving at least one bead.

outputFormat

The function should return a vector<long long> (or equivalent in your language) of length N. The k^th element of the array should represent the minimized worst-case total fee (in yuan) required to eventually isolate the magic bead when starting with k ordinary beads (and one magic bead).

sample

N = 3
A = [1, 2]
B = [1, 1]

0 3 6