OohMoo Milk
플래티넘 I의견: 0
Farmer John is trying to make his world's famous OohMoo Milk to sell for a
profit. He has \(N\) \((1 \leq N \leq 10^5)\) bottles that he is trying to fill.
Each bottle initially contains some amount of milk \(m_i\)
\((0 \leq m_i \leq 10^9)\). Every day, he takes \(A\) \((1 \le A \le N)\) bottles and
fills each bottle with one unit of milk.
Unfortunately, Farmer Nhoj, Farmer John's competitor in the business of OohMoo
Milk, knows about Farmer John's production processes and has a plan to curtail
his business. Every day, after Farmer John fills his \(A\) bottles, Farmer Nhoj
will sneakily steal one unit of milk from each of \(B\) \((0 \le B < A)\) different
nonempty bottles. To remain sneaky, Farmer Nhoj chooses \(B\) so that it is
strictly less than \(A\), so that it is less likely for Farmer John to discover
him.
After \(D\) (\(1 \leq D \leq 10^9\)) days, Farmer John will sell his OohMoo Milk. If
a bottle has \(M\) units of milk, it will sell for \(M^2\) moonies.
Let \(P\) be the unique profit such that FJ can guarantee that he makes at least
\(P\) profit regardless of how FN behaves, and FN can guarantee that FJ makes at
most \(P\) profit regardless of how FJ behaves. Output the value of \(P\) modulo
\(10^9+7\).
Problem credits: Suhas Nagar
SCORING
- Inputs 4-6: \(N,D\le 1000\).
- Inputs 7-10: \(D\le 10^6\).
- Inputs 11-20: No additional constraints.
Problem credits: Suhas Nagar
The first line of the input contains \(N\) and \(D\), where \(N\) is the number of
bottles and \(D\) is the number of days that take place.
The second line of the input contains \(A\) and \(B\) representing the number of
units of milk that Farmer John fills and Farmer Nhoj steals respectively.
The third line of the input contains \(N\) space-separated integers \(m_i\)
representing the initial amount of milk in each bottle.
Output the value of \(P\) modulo \(10^9+7\).
5 4
4 2
4 10 8 10 10546On the first day, Farmer John could add milk to the second, third,
fourth, and fifth bottles. Then, Farmer Nhoj could remove milk from the
second and fourth bottles.
Thus, the new amount of milk in each bottle is
$$ [4, 10, 8, 10, 10] \to [4, 11, 9, 11, 11] \to [4, 10, 9, 10, 11]. $$
After four days, the amount of milk in each bottle could be
$$ [4, 10, 8, 10, 10] \to [4, 10, 9, 10, 11] \to [4, 10, 10, 11, 11] \to [4, 11, 11, 11, 11] \to [4, 11, 11, 12, 12]. $$
The total amount of moonies Farmer John would make in this situation is \(4^2+11^2+11^2+12^2+12^2 = 546\). It can be shown that this is the value
of \(P\).
10 5
5 1
1 2 3 4 5 6 7 8 9 107775 1000000000
3 1
0 1 2 3 410Make sure you output \(P\) modulo \(10^9+7\).
평가 및 의견
OohMoo Milk
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
OohMoo Milk