# HackerEarth Benny and Balls problem solution

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