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


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;
}