**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!
↵
**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!
