No.2834 Work to Play
タグ : / 解いたユーザー数 9
作問者 :
Problem Statement
Having spent too much money on a Japanese drum game, I decided to earn money with a part-time job collecting carts at a supermarket.
Along a half-line passage extending in one direction from the supermarket, there are $N$ cart stations, and cart station $i \ (1 \leq i \leq N)\ $ is located at distance $i$ from the supermarket.
It is known that $Ai$ carts have accumulated at cart station $i$. Up to $K$ carts can be carried at $1$ time.
Therefore, I decided to collect all the carts using the following strategy.
$1$. If there are cart stations with $K$ or more carts, choose $1$ of them and keep carrying $K$ carts at a time from that cart station until fewer than $K$ carts remain there.
$2$. Once every cart station has fewer than $K$ carts, go to the cart station farthest from the supermarket among those that have carts, then, on the way back, greedily gather carts until reaching $K$ carts and carry them. In other words, carry $K$ carts among the carts currently placed, starting from those farthest from the supermarket.
Find the distance traveled when this strategy is carried out and all the carts have been collected at the supermarket, modulo $998244353$. Note that no carts are added during the collection, and that when collecting, I head by the shortest route to the cart stations from which carts are to be collected.
Input
$N\ A\ K$
・$1 \leq N \leq 10^{16}$
・$1 \leq A < K$
・$2 \leq K \leq 10^5$
・$N,A,K$ are all integers
Output
Output the distance traveled when all the carts have been collected, modulo $998244353$.
Sample
Sample 1
Input
3 5 6
Output
26
Initially, there are $5$ carts at cart station $1$, $10$ carts at cart station $2$, and $15$ carts at cart station $3$. First, to get below $6$ carts, carry carts $1$ time from cart station $2$ and $2$ times from cart station $3$. The cart stations then have $5$, $4$, and $3$ carts remaining, respectively.
After that, carry $3$ carts from cart station $3$ together with $3$ carts from cart station $2$, and then collect the remaining carts. The total distance traveled is $26$.
Sample 2
Input
1 1 10
Output
2
$1$ trip of carrying carts may involve fewer than $K$ carts.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。