No.3097 Azuki Kurai
RiRinbaru
ygussany
autumn09
Yotugi
hamo21Problem Statement
$N$ villagers live in houses arranged in a circle. One particular house is defined as house $1$, and going clockwise from it, the houses are defined as houses $2, 3, ..., N$.
Each villager has azuki beans, and the amount of azuki held by the villager living in house $i$ is given as $A_i$ using the sequence $A=(A_1, A_2, ..., A_N)$.
Every night, a youkai named RiRinbaru sneaks into a villager's house and eats all the azuki in that house. The villagers do not want the youkai to take their azuki, so each day they can move $K$ of azuki to neighboring houses. That is, every villager chooses an amount of their own azuki that is a non-negative integer not exceeding $K$, splits it into $2$ non-negative integer amounts, and then moves each of them to the house of one of the two neighbors. An amount in the split may be $0$.
Formal Definition
The following 2 operations, occurring in this order, together constitute what happens in $1$ day.- For house $i(1\leq i\leq N)$, perform the following operation for all houses simultaneously. Choose a non-negative integer between $0$ and $K$, inclusive, and reduce the azuki of the villager living in that house by that amount. The azuki cannot be reduced so that the amount in the house becomes less than $0$. Then, split the removed azuki into 2 non-negative integer amounts that are at least $0$. Then, add those amounts to the azuki held by houses $i-1, i+1$, respectively. Here, house $0$ denotes house $N$, and house $N+1$ denotes house $1$.
- RiRinbaru sneaks into one house. The amount of azuki in that house becomes $0$.
Thanks to a fortune teller, the house RiRinbaru will sneak into on each of the next $M$ days is known. Specifically, the house sneaked into on day $i$ is represented as $B_i$ using the sequence $B=(B_1, B_2,..., B_M)$.
Output the answer to the following problem for each of $i=1, 2, ..., M$.
Find the maximum possible total amount of uneaten azuki in the whole village after $i$ days.
Input
$N\ M\ K$ $A_1\ A_2\ ...\ A_N$ $B_1\ B_2\ ...\ B_M$
- $3\leq N\leq 9$
- $1\leq M\leq 2×10^3$
- $1\leq K\leq 10^9$
- $0\leq A_i\leq 10^9(1\leq i\leq N)$
- $1\leq B_i\leq N(1\leq i\leq M)$
- All inputs are integers.
Output
Output the maximum possible total amount of uneaten azuki in the whole village after $i\ (1\leq i\leq M)$ days, for each such day.
Print a newline after each line, including at the end.
Sample
Sample 1
Input
4 2 10 21 10 30 40 2 1
Output
101 100
On day 1, RiRinbaru sneaks into house $2$, so to keep the azuki from being eaten, move all the azuki in house $2$ to house $3$. Also, move $10$ of the azuki in house $1$ to house $4$.
In this case, $101$ azuki remain across the $4$ houses. The amount of azuki never increases from the initial total, so this is the maximum, and you should output 101.
On day 2, RiRinbaru sneaks into house $1$, so to keep the azuki from being eaten, move $10$ of the azuki in house $1$ to house $4$. As a result, the $1$ azuki remaining in house $2$ is eaten.
In this case, $100$ azuki remain across the $4$ houses. There is no way of moving that prevents all the azuki from being eaten, and this way of moving is one of those that achieve the maximum amount of uneaten azuki, so you should output 100.
Sample 2
Input
3 3 100000000 70000000 100000000 130000000 2 1 3
Output
300000000 300000000 300000000
There is a way of moving that keeps all the azuki from being eaten over all 3 days, so output the sum of $A_i(1\leq i\leq N)$, which is 300000000, $3$ times.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。