HackerEarth Benny and Balls problem solution YASH PAL, 31 July 2024 In this HackerEarth Benny and Balls problem solution In this problem, Benny is looking for your help as usual. There are N baskets, which are numbered from 0 to N – 1. In each moment of time exactly, starting with t = 1, one ball appears in xi-th basket, where xi = (a * x(i-1) + b) % N. The bottom of the i-th basket opens when there are not less than the p[i] balls in it, all the balls fall out of the basket, and then the bottom of the basket is closed again. How many times baskets’ bottoms will open to the T-th moment of time? HackerEarth Benny and Balls problem solution. #include <bits/stdc++.h>using namespace std;const long long N = (long long)1e5 + 10;long long n, a, b, x, t;long long p[N], add[N], id[N], sum[N];long long ans = 0;long long xb, tb;void read_data(){ cin >> n; for (int i = 0; i < n; ++i) cin >> p[i]; cin >> x >> a >> b >> t; xb = x; tb = t;}long long solve(){ long long px = x; long long tt = t; for (int i = 0; i < n; ++i) add[i] = sum[i] = 0, id[i] = -1; long long xc = x; long long step = 0; while (!add[xc]){ add[xc]++; id[xc] = step++; xc = (a * xc + b) % n; } long long cycleLen = step - id[xc]; long long preCycleLen = step - cycleLen; for (int i = 0; i < min(t, preCycleLen); ++i){ sum[x]++; x = (1LL * a * x + b) % (long long)n; } t -= min(t, preCycleLen); int cntCycles = t / cycleLen; for (int i = 0; i < cycleLen; ++i){ sum[x] += cntCycles; x = (1LL * a * x + b) % (long long)n; } t %= cycleLen; for (int i = 0; i < t; ++i){ sum[x] += 1; x = (a * x + b) % n; } long long ans = 0; for (int i = 0; i < n; ++i) ans += sum[i] / p[i]; x = px; t = tt; return ans;}void write_data(long long ans){ cout << ans << endl;}long long bs[N];long long brute(){ long long ans = 0; for (int i = 0; i < n; ++i) bs[i] = 0; for (int i = 0; i < tb; ++i){ bs[xb]++; xb = (a * xb + b) % n; } for (int i = 0; i < n; ++i) ans += bs[i] / p[i]; return ans;}int main(){ ios_base::sync_with_stdio(false); srand(time(NULL)); int cnt; cin >> cnt; while (cnt--){ read_data(); write_data(solve()); } return 0;} Second solution #include<bits/stdc++.h>using namespace std;const int INF = 1e9;const int N = 100031;int tests, n, cnt[N];int x, a, b, t, p[N];int main(){ ios_base::sync_with_stdio(0); cin >> tests; for (; tests; --tests) { cin >> n; for (int i = 0; i < n; i++) { cin >> p[i]; cnt[i] = 0; } cin >> x >> a >> b >> t; int ans = 0; for (int i = 1; i <= t; i++) { cnt[x]++; if (cnt[x] >= p[x]) { ans++; cnt[x] = 0; } x = (1ll * x*a + b) % n; } cout << ans << endl; } return 0;} coding problems