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: