C - 长序列

分数：300分

题目描述

我们有一个由$N$个正整数组成的序列：$A=(A_1,\dots,A_N)$.
令$B$表示$A$的$10^{100}$个拷贝的连接。

考虑从左到右依次对$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$

输出

输出答案。

3
3 5 2
26

8

我们有$B=(3,5,2,3,5,2,3,5,2,\dots)$.
$\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26}$成立，但当$k$是7或更小时，条件不满足，所以答案是8。

4
12 34 56 78
1000

23