102584: [AtCoder]ABC258 E - Packing Potatoes
Description
Score : $500$ points
Problem Statement
$10^{100}$ potatoes are coming from a conveyor belt one by one. The weights of the potatoes are described by a sequence $W = (W_0, \dots, W_{N-1})$ of length $N$: the weight of the $i$-th potato coming is $W_{(i-1) \bmod N}$, where $(i-1) \bmod N$ denotes the remainder when $i - 1$ is divided by $N$.
Takahashi will prepare an empty box and then pack the potatoes in order, as follows.
- Pack the incoming potato into the box. If the total weight of the potatoes in the box is now $X$ or greater, seal that box and prepare a new empty box.
You are given $Q$ queries. In the $i$-th query $(1 \leq i \leq Q)$, given a positive integer $K_i$, find the number of potatoes in the $K_i$-th box to be sealed. It can be proved that, under the Constraints of the problem, there will be at least $K_i$ sealed boxes.
Constraints
- $1 \leq N, Q \leq 2 \times 10^5$
- $1 \leq X \leq 10^9$
- $1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)$
- $1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $Q$ $X$ $W_0$ $W_1$ $\ldots$ $W_{N-1}$ $K_1$ $\vdots$ $K_Q$
Output
Print $Q$ lines. The $i$-th line $(1 \leq i \leq Q)$ should contain the answer to the $i$-th query.
Sample Input 1
3 2 5 3 4 1 1 2
Sample Output 1
2 3
Before sealing the $2$-nd box, Takahashi will do the following:
- Prepare an empty box.
- Pack the $1$-st potato into the box. Now, the total weight of potatoes in the box is $3$.
- Pack the $2$-nd potato into the box. Now, the total weight of potatoes in the box is $3 + 4 = 7$, which is not less than $X = 5$, so seal this box.
- Prepare a new empty box.
- Pack the $3$-rd potato into the box. Now, the total weight of potatoes in the box is $1$.
- Pack the $4$-th potato into the box. Now, the total weight of potatoes in the box is $1 + 3 = 4$.
- Pack the $5$-th potato into the box. Now, the total weight of potatoes in the box is $1 + 3 + 4 = 8$, which is not less than $X = 5$, so seal this box.
The $1$-st box sealed contains $2$ potatoes, and the $2$-nd box sealed contains $3$ potatoes.
Sample Input 2
10 5 20 5 8 5 9 8 7 4 4 8 2 1 1000 1000000 1000000000 1000000000000
Sample Output 2
4 5 5 5 5
Input
题意翻译
给定序列 $ W $,下标范围为 $ [0, n - 1] $。存在一个长度为 $ 10^{100} $ 的土豆序列,循环节为 $ n $,第 $ i $ 个土豆的重量为 $ W_{(i - 1) \bmod{n}} $。现在你需要用箱子装土豆,每个箱子装满则停止,即土豆重量恰好大于等于 $ X $ 时则停止。$ Q $ 组询问求第 $ k_i $ 个箱子装了多少个土豆。Output
分数:$500$分
问题描述
有一个传送带会逐一地运送$10^{100}$个土豆。这些土豆的重量可以用长度为$N$的序列$W = (W_0, \dots, W_{N-1})$来描述:第$i$个运来的土豆的重量是$W_{(i-1) \bmod N}$,其中$(i-1) \bmod N$表示将$i - 1$除以$N$的余数。
高桥将会准备一个空箱子,然后按照顺序将土豆装入,如下所示。
- 将运来的土豆装入箱子。如果现在箱子中土豆的总重量是$X$或更大,那么将这个箱子密封起来,并准备一个新的空箱子。
你将收到$Q$个查询。在第$i$个查询$(1 \leq i \leq Q)$中,给定一个正整数$K_i$,找出将要被密封的第$K_i$个箱子中的土豆数量。可以证明,在问题的约束下,至少会有$K_i$个被密封的箱子。
约束
- $1 \leq N, Q \leq 2 \times 10^5$
- $1 \leq X \leq 10^9$
- $1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)$
- $1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)$
- 输入中的所有值都是整数。
输入
输入将从标准输入中给出以下格式:
$N$ $Q$ $X$ $W_0$ $W_1$ $\ldots$ $W_{N-1}$ $K_1$ $\vdots$ $K_Q$
输出
打印$Q$行。第$i$行$(1 \leq i \leq Q)$应包含第$i$个查询的答案。
样例输入1
3 2 5 3 4 1 1 2
样例输出1
2 3
在密封第二个箱子之前,高桥将会做以下事情:
- 准备一个空箱子。
- 将第1个土豆装入箱子。现在,箱子中土豆的总重量是$3$。
- 将第2个土豆装入箱子。现在,箱子中土豆的总重量是$3 + 4 = 7$,这并不小于$X = 5$,所以将这个箱子密封起来。
- 准备一个新的空箱子。
- 将第3个土豆装入箱子。现在,箱子中土豆的总重量是$1$。
- 将第4个土豆装入箱子。现在,箱子中土豆的总重量是$1 + 3 = 4$。
- 将第5个土豆装入箱子。现在,箱子中土豆的总重量是$1 + 3 + 4 = 8$,这并不小于$X = 5$,所以将这个箱子密封起来。
被密封的第一个箱子中包含2个土豆,被密封的第二个箱子中包含3个土豆。
样例输入2
10 5 20 5 8 5 9 8 7 4 4 8 2 1 1000 1000000 1000000000 1000000000000
样例输出2
4 5 5 5 5