← 返回题目列表

AtCoder · abc220_c

E. 长序列

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

分数: 300 点

问题陈述

我们有一系列 N 正整数: A=(A_1,\dots,A_N).
让 B 是以下的串联 10^{100} 副本 A.

考虑总结以下条款 B 从左到右。什么时候总和超过 X 第一次?
换句话说,求最小整数 k 这样:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq X \leq 10^{18}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 \ldots A_N
X

输出

打印答案。


示例输入 1

3
3 5 2
26

示例输出 1

8

我们有 B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} 成立,但当 k is 7 或更少,所以答案是 8.


示例输入 2

4
12 34 56 78
1000

示例输出 2

23