問題一覧 > 通常問題

No.2834 Work to Play

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : twitteryou / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11034 / 自分の提出
問題文最終更新日: 2024-08-01 16:52:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 439 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。