/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の正整数のみからなる数列 A=(A_1,\dots,A_N) があります。
A を 10^{100} 回連結した数列を数列 B とします。
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
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