← 返回题目列表

AtCoder · joi2022ho_a

A. 星际

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

配点: 100 点

問題文

时间是 \mathrm{30XX} 年。在科学家和工程师的不懈努力下,不同星球之间的交流变得更加普遍。海狸 Bitaro 正在担任向外星人介绍地球食物的大使,并计划于今天下午 1 点出发前往 JOI 星球。

这次我们要向JOI Alien介绍的食物之一是切碎的卡斯提拉。 Castella 是一种柔软的海绵状糖果,是在小麦粉中添加鸡蛋、糖和淀粉糖浆制成的。

卡斯特拉的形状像一个水平长的长方体,并且卡斯特拉的形状像一个长方体。 它被分为 N 块。从左边开始 i 番目 (1 \leqq i \leqq N) 片段长度为整数 A_i 。

最近发现JOI外星人表现出对偶数的厌恶。作为解决方法,我决定重复以下一系列操作,直到没有长度均匀的片段为止。

  1. 选择最右边的长度相等的片段。
  2. 纵向剪切选定的部分。 2 分成相等的部分。换句话说,所选片段的长度是 k ,我们可以改变片段的长度而不改变它的位置。 \displaystyle\frac{k}{2} 片 分为 2 。

为了检查操作是否正确执行,Bitaro 我已经准备了 Q 问题。j 番目 (1 \leqq j \leqq Q) 的问题如下。

  • 当所有操作完成后,从左开始 第 X_j 块的长度是多少?

给定城堡和问题信息,编写一个程序来查找每个问题的答案。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

N
A_1
A_2
\vdots
A_N
Q
X_1
X_2
\vdots
X_Q

出力

到标准输出 输出 Q 行。j 行目 (1 \leqq j \leqq Q)有 打印第j 问题的答案。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N).
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq X_j \leqq 1\,000\,000\,000\,000\,000\ (= 10^{15}) (1 \leqq j \leqq Q).
  • X_{j} \leqq X_{j + 1} (1 \leqq j \leqq Q - 1).
  • 当所有操作完成后,Castella 它被分成 X_Q 或更多块。

小課題

  1. (25 点) A_i \leqq 8 (1 \leqq i \leqq N).
  2. (35 点) N \leqq 1\,000,Q \leqq 1\,000.
  3. (40 点)没有额外的限制。

入力例 1

4
14
9
8
12
6
2
3
5
7
11
13

出力例 1

7
9
1
1
1
3

最初,每块卡斯特拉的长度是从左边开始的。 14, 9, 8, 12 。

当这一系列操作完成后,卡斯特拉 它被分成 15 块,每块的长度从左开始按顺序显示。 7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3 变为。

这个输入/输出示例是一个小任务。 2, 3 满足约束。


入力例 2

13
1
4
1
4
2
1
3
5
6
2
3
7
3
8
2
10
11
13
15
17
18
20

出力例 2

1
1
1
1
5
3
1
3

此输入/输出示例满足所有子任务约束。


入力例 3

16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704

出力例 3

5
1
7
57
1

这个输入/输出示例是一个小任务。 2, 3 满足约束。