← 返回题目列表

AtCoder · abc258_e

H. 包装土豆

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

10^{100} 土豆从传送带上一颗一颗地送来。土豆的重量由序列描述 W = (W_0, \dots, W_{N-1}) 长度 N:重量 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

密封之前 2-nd 框中,高桥将执行以下操作:

  • 准备一个空盒子。
  • 打包 1-st土豆入盒。现在,盒子里土豆的总重量是 3.
  • 打包 2-将土豆放入盒子中。现在,盒子里土豆的总重量是 3 + 4 = 7,不小于 X = 5,所以密封这个盒子。
  • 准备一个新的空盒子。
  • 打包 3-rd土豆放入盒子中。现在,盒子里土豆的总重量是 1.
  • 打包 4第一个土豆放入盒子中。现在,盒子里土豆的总重量是 1 + 3 = 4.
  • 打包 5第一个土豆放入盒子中。现在,盒子里土豆的总重量是 1 + 3 + 4 = 8,不小于 X = 5,所以密封这个盒子。

的 1-st 密封盒包含 2 土豆,以及 2-nd 盒子密封包含 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