Official
C - Long Sequence Editorial by en_translator
Let \(K\) be the desired answer.
Let us denote \(sumA= \sum_{i=1}^{N} A_i\).
\(\{B_1 , \dots , B_K\}\) is a concatenation of some (say, \(p\) number of) copies of \(A\), followed by some (say, \(q\) number of) first terms of \(A\).
Here, we assume \(p \geq 0, 1 \leq q \leq N\).
Now let us find \(p\) and \(q\).
\(p\) can be obtained by \( p={ \lfloor \frac{X}{sumA} \rfloor}\).
\(q\) can be obtained by naively summing up \(A_i\)’s, in an \(O(N)\) computation time.
Now we have the answer \(K=p \times N+q\), so the problem has been solved.
Here is a sample code in C++.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
ll n;cin>>n;
vector<ll> a(n);
for(int i=0;i<=n-1;i++)cin>>a[i];
ll x;cin>>x;
ll sum=0;
for(ll val:a)sum+=val;
ll P = x / sum;
ll sumb = P * sum;
ll ans = P * n;
for(ll val:a){
sumb += val;
ans++;
if(sumb > x){
cout<< ans <<endl;
return 0;
}
}
return 0;
}
posted:
last update: