102202: [AtCoder]ABC220 C - Long Sequence
Description
Score : $300$ points
Problem Statement
We have a sequence of $N$ positive integers: $A=(A_1,\dots,A_N)$.
Let $B$ be the concatenation of $10^{100}$ copies of $A$.
Consider summing up the terms of $B$ from left to right. When does the sum exceed $X$ for the first time?
In other words, find the minimum integer $k$ such that:
$\displaystyle{\sum_{i=1}^{k} B_i \gt X}$.
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq X \leq 10^{18}$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $A_1$ $\ldots$ $A_N$ $X$
Output
Print the answer.
Sample Input 1
3 3 5 2 26
Sample Output 1
8
We have $B=(3,5,2,3,5,2,3,5,2,\dots)$.
$\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26}$ holds, but the condition is not satisfied when $k$ is $7$ or less, so the answer is $8$.
Sample Input 2
4 12 34 56 78 1000
Sample Output 2
23
Input
题意翻译
有一个长度为$ N $的正整数数组$A=(A_1, A_2,A_3,\dots,A_n)$. 将A数组复制$10^{100}$份，得到数组$ B $。 将数组$ B $从左到右依次累加，问第一次超过$ X $是在哪个位置？ 形式化的描述这个问题如下： 求满足下面条件的最小的$ k $值。 $ \sum\limits_{i=1}^kB_i > X$Output
分数：$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$
输出
输出答案。
样例输入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$为7或更小时，条件不成立，所以答案为8。
样例输入2
4 12 34 56 78 1000
样例输出2
23