Problem: https://atcoder.jp/contests/abc220/tasks/abc220_c

The Idea: A straightforward approach is to keep adding elements until the sum exceeds X. But when X is very large, this can be too slow.

Instead, calculate the sum of one complete array. Use integer division to skip as many complete repetitions as possible, then process the remaining elements one by one.

C++ Solution

#include <bits/stdc++.h> 
using namespace std; 


int main() 
{ 
    long long n; 
    cin >> n; 

    vector<long long> a(n); 
    long long total = 0; 

    for (int i = 0; i < n; i++) 
    { 
        cin >> a[i]; 
        total += a[i]; 
    } 

    long long x; 
    cin >> x; 

    long long cycles = x / total; 
    long long sum = cycles * total; 
    long long count = cycles * n; 

    for (int i = 0; i < n; i++) 
    { 
        sum += a[i]; 
        count++; 

        if (sum > x) 
        { 
            cout << count << '\n'; 
            return 0; 
        } 
    } 

    return 0;
}

What Can You Learn? - Why a brute-force approach can be too slow. - How to use maths to skip repeated operations. - How to turn a straightforward solution into an efficient one.

NOTE:

I'm a beginner myself, and I really enjoyed solving this problem, so I thought I'd share it. If you spot any mistakes, feel free to point them out!